Its a DP problem:
Let L[j] be the length of the longest increasing sub sequence including jth array element.
=> L[i] = MAX(L[j]+1) for all (j<i)&&(a[j]<=a[i]).
O(n^2) solution.
http://www.geeksforgeeks.org/archives/12832
Let L[j] be the length of the longest increasing sub sequence including jth array element.
=> L[i] = MAX(L[j]+1) for all (j<i)&&(a[j]<=a[i]).
O(n^2) solution.
http://www.geeksforgeeks.org/archives/12832
No comments:
Post a Comment