This is, drawing on the idea of LCS using DP. Think, this works.
Given array A[1..n] and k, fill up two more arrays ,
lcs[j] = max_{i=1 to j-1} lcs[i] , where A[i] <= A[j]
maxPrevindex[j] = i , where A[i] is max among all A[i], such that A[i]
<= A[j] and i ranging over 1 to j-1
This can be done in O(n^2).
Now compute
maxSum[j] = A[j] if lcs[j] == 1
= A[j]+ maxSum[ maxPrevindex[j] ] otherwise
if( lcs[j] <= k for all j )
answer = MAX ( maxSum[j] ) , lcs[j] == k
else
for all j, st. lcs[j] > k
move down the maxPrevindex[j] chain k times , to say
j'
update maxSum[j] = maxSum[j] - maxSum[j']
end for
answer = MAX ( maxSum[j] ) , lcs[j] >= k
end if
O(n^2) time, O(n) space
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
