Very Nice soln Dhritiman.
The solution to the standard LCS problem only needs O(n^2) time and O(n)
space.
And you have very intelligently solved its variation also in the same time
and space complexity.
I fell this is the correct solution.
Nikhil Jindal
On Tue, Aug 31, 2010 at 2:13 AM, Dhritiman Das <dedhriti...@gmail.com>wrote:
>
> 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 algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
Please access the attached hyperlink for an important electronic communications
disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
