[algogeeks] Re: How to find, efficiently, the maximum sum of atleast L consecutive integers from a sequence of N integers.

[geek4u]

@aj if we dont want the substring , then my code wll work with a slight modification for the problem i.e. take 2 variables to count the substring length in the code. And in this case it doesnt requires dynamic programming.

On 3/21/06, aj <[EMAIL PROTECTED]> wrote:

Consider a specific case of this problem where L = 1, which corresponds
to the problem of
finding a substring with maximum sum. This problem can be easily solved
using dynamic programming in O(n) as shown below:

construct an array A[1,2...n], such that A[i] denotes the largest sum
of a substring with starting point a_i.

A[i]  = a_i      if A[i + 1] is negative
        = a_i  + A[i + 1]         otherwise.

Now come back to the original problem and in a similar way construct
the array B[1,2...n], such that B[i] denotes the largest sum of a
substring starting at a_i and has length at least L. Note that B can be
constructed using the recurrence

B[i]  =  a_i  + a_{i+1} +.....a_{i + L - 1}   + A[i + L -1];

once we have all the B[i]'s, choosing maximum of them should not be a
difficult task.
time complexity = O(n)  which is the best that can be achieved

--
Ajay kr. Mishra
http://ajay.mishra19.googlepages.com
IIT KGP
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---