Sorry. I did not fully understand your suggestion.
But one thing for certain - you might have to include negative numbers
also in your subsequence as it might be accompanied by huge positive
numbers before & after.
Solution:
0. given array A[0..n]
1. find cumulative sums in B[0..n] can also be done in-place
B[0] = 0; B[i] = B[i-1]+A[i]
2. find location of minimum number before it in C
C[0] = 0; C[i] = (B[C[i-1]]>B[i])? C[i-1]: i
3. for (i=L; i<n; i++)
MAX = maximum { B[i] - B[C[i-L]], MAX }
Cost: O(n) for each step {O(n-k) for the last}
Many variations of this, all solvable in O(n) cost can be found, though
its very tempting to use O(kn) for maximizing sum of atmost k numbers.
-
Regards
[EMAIL PROTECTED]
B.Tech (CSE), IIT Kanpur '03
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
