A simpler problem is to find the length of the longest increasing subsequence. You can focus on understanding that problem first. The only difference in the algorithm is that it doesn’t use the P array. x is the input of a sequence, so it can be initialized as: x = [0, 8, 4, 12, 2, … Read more
Let’s first look at the n^2 algorithm: dp[0] = 1; for( int i = 1; i < len; i++ ) { dp[i] = 1; for( int j = 0; j < i; j++ ) { if( array[i] > array[j] ) { if( dp[i] < dp[j]+1 ) { dp[i] = dp[j]+1; } } } } Now … Read more
OK, I will describe first the simplest solution which is O(N^2), where N is the size of the collection. There also exists a O(N log N) solution, which I will describe also. Look here for it at the section Efficient algorithms. I will assume the indices of the array are from 0 to N – … Read more