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
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.