CODERE3 - Coder Express 3!! is very easy DP problem.
I've solved this problem in O(n^2), but there is a better solution also, which runs in O(n(logn)) time complexity.
This problem is based on longest increasing sub-sequence (link for n*logn recursive DP for LIS).
There are two arrays, l[] and r[]. ith index of l[] tells the longest increasing sub-sequence till ith element, and same is for r[].
For finding longest increasing sub-sequence, we will traverse i 0 to n, and j from i+1 to n, and will check following conditions:
if (a[i] < a[j] && l[j] < l[i] + 1)
l[j] = l[i] + 1
And by doing same thing in reverse order, we can get r[].
After calculating l[] and r[], we will find the point where l[i] + r[i] is max.
This was explanation for O( n^2 ), now try to think solving this problem in O(n(logn)).
If you find any difficulty in coding part, refer to the following code:
0 comments:
Post a Comment