Help for a Biologist

[wsafdbv]

For a major simulation project in our lab, we are receiving a series of integers from the lab equipment (note: we usually have in excess of 100 numbers per simulation). These numbers represent some actions of an ant colony. We need to return the number of elements in the largest set possible of strictly increasing numbers, where strictly increasing numbers are defined as the set of numbers where each number is greater then or equal to the previous one. The order of the numbers _does_ matter and the numbers cannot be resorted in any way. For example, the set
7 4 3 5 10 34 19 1 28
has the following sets of strictly increasing numbers:
7 10 34
4 5 10 34
3 5 10 34
10 34
34
19 28
28
In this case, we would need to report 4. We have working code, however, it is very slow and only works for short examples of 5 or fewer elements. This makes it useless for us, and it is very time consuming to have a human be responsible for doing this on a set of 100 numbers! Does anyone know how to code this in an efficient way? If so, what would be the big-oh of your code? Please help me.
PS This should be coded in Java.

[server_crash]

What exactly do you want us to do? We're not going to do your homework.

[iamthwee]

>Does anyone know how to code this in an efficient way?

Well I can think of an solution which would have about the same time complexity of bubble sort. I.e using a nested for loop. But that's not efficient.

>(note: we usually have in excess of 100 numbers per simulation).

100, that number is nothing for a program. I could use a grossly inefficient algorithm and get the output desired in little to no time at all.

Here's a test program I've just written in just 13 lines of code:

The set:

59 52 50 14 29 59 94 13 13 58 82 57 100 55 90 66 98 28 6 23 71 22 79 84 63 41 32
 66 21 7 13 88 7 73 63 63 69 67 58 9 88 56 70 11 21 50 43 46 87 26 5 97 21 31 4
93 27 72 32 94 86 24 43 88 73 34 5 45 47 31 33 55 75 54 55 19 11 82 81 91 16 36
49 66 97 17 11 90 62 36 19 14 15 43 90 24 89 66 6 93

The output:

59 94 100
52 59 94 100
50 59 94 100
14 29 59 94 100
29 59 94 100
59 94 100
94 100
13 58 82 100
13 58 82 100
58 82 100
82 100
57 100
100
55 90 98
90 98
66 98
98
28 71 79 84 88 97
6 23 71 79 84 88 97
23 71 79 84 88 97
71 79 84 88 97
22 79 84 88 97
79 84 88 97
84 88 97
63 66 88 97
41 66 88 97
32 66 88 97
66 88 97
21 88 97
7 13 88 97
13 88 97
88 97
7 73 88 97
73 88 97
63 69 88 97
63 69 88 97
69 88 97
67 88 97
58 88 97
9 88 97
88 97
56 70 87 97
70 87 97
11 21 50 87 97
21 50 87 97
50 87 97
43 46 87 97
46 87 97
87 97
26 97
5 97
97
21 31 93 94 97
31 93 94 97
4 93 94 97
93 94 97
27 72 94 97
72 94 97
32 94 97
94 97
86 88 91 97
24 43 88 91 97
43 88 91 97
88 91 97
73 75 82 91 97
34 45 47 55 75 82 91 97
5 45 47 55 75 82 91 97
45 47 55 75 82 91 97
47 55 75 82 91 97
31 33 55 75 82 91 97
33 55 75 82 91 97
55 75 82 91 97
75 82 91 97
54 55 82 91 97
55 82 91 97
19 82 91 97
11 82 91 97
82 91 97
81 91 97
91 97
16 36 49 66 97
36 49 66 97
49 66 97
66 97
97
17 90 93
11 90 93
90 93
62 90 93
36 43 90 93
19 43 90 93
14 15 43 90 93
15 43 90 93
43 90 93
90 93
24 89 93
89 93
66 93
6 93
93

Think...

Btw your sample output is wrong. It should be:

7 10 34
4 5 10 34
3 5 10 34
10 34
34
19 28
1 28 <---missed
28

[wsafdbv]

Thanks iamthwee for your help.
No, in fact this is not my homework. It is a real problem that we are studying at a research laboratory in Arkansas and that I am paid to do. Being trained as a biologist 20 years ago, I do not know many advanced coding styles, despite the computational nature of our problem. All I was asking was for a hint on how to get started.
Thanks again.

[iamthwee]

You better not be lying... people try all sorts of tricks these days including me. Tee he he.

Here's the pseudo code, I'll leave it to you to write in java.

for ( int i = 0; i<array.size(); i++ )
    {
        int temp=0;
        for( int j = 0; j<array.size(); j++ )
        {
            if(j>=i)
            {
                if( array[j]>temp )
                {
                    temp = array[j]; //update temp
                    print(array[j]+" ");
                } 
            }
        }
        
        print("\n");           
            
     }

Btw, that's the not so efficient one. I have another which is reduce in time complexity. If you beg I may give it you. :cheesy:

[Phaelax]

Who would pay someone with no programming experience to code such a simple problem?

Same basic code as iamthwee posted, except for a small change.

int[] array = {45,89,65,52,5,68,7,2,24,17,35,84,65,99,54,32,7,66,98,15,35,45,65,75,37,15};
		
		for (int i=0; i<array.length; i++)
		{
			int temp = -1;
			for (int j=i; j<array.length; j++)
			{
				if (array[j] > temp)
				{
					temp = array[j];
					System.out.print(array[j]+", ");
				}
			}
			System.out.println();
		}