|
The only other idea i have is a spin off of brute forcing it. Go through the string counting every time it goes up, but then save the location it decreases so you know where to start from next time. See the example below:
Data: 3,5,8,10,4,7,12,2,17
When it hits the 4, it saves the location and continues.
I would have a temp variable to hold it and have its default value set as -1 so if it finishes with a -1 it knows it's finished and if there is a decrease and it's not -1 then it wont overwrite it.
Then the next time through the loop it starts at the location of the 4 since it is pointless to check the 5,8, or 10. Then continue the cycle comparing the length of the subsequences each time to store the greatest one. This will get you the longest increasing subsequence.
To get all of them, just do the same thing but store each iteration through the loop.
I hope this makes a little sense.
|