A monotone increasing subsequence is a subset of numbers which are strictly increasing from left to rght. This definition does not require that the numbers be adjacent in the original set or that the longest sequence is unique. Ex.
1 2 9 4 7 3 11 8 14 6
The sequence 1 2 4 7 11 14 is the longest subsequence.
First if you can find out the length of longest subsequence that can end with a particular number, then we can choose the subsequence with maximum length. Now the problem is to find the longest subsequence which ends with a particular number.
Array Index