0

Possible Duplicate:
Maximum Contiguous Subsequence Sum of At Least Length L

Let X = {x1, x2, · · · , xn} be a sequence of arbitrary numbers (positive or negative). Give an O(n) time algorithm to find the subsequence of consecutive elements xi,xi+1,···,xj whose sum is maximum over all consecutive subsequences. For example, for X = {2,5, −10, 3, 12, −2, 10, −7, 5}, {3, 12, −2, 10} is a solution.

Community
  • 1
  • 1
GG2012
  • 1
  • 1
  • If it is the case, please tag homework questions as `homework`; mentioning how you've approached the problem so far can also help. If not homework please ignore. – ninjagecko Oct 05 '12 at 05:50
  • @ninjagecko: [The homework tag is now officially deprecated](http://meta.stackexchange.com/questions/147100/the-homework-tag-is-now-officially-deprecated). – Jerry Coffin Oct 05 '12 at 05:51
  • Thank You Guys...No this is not a homework problem...found in it my GATE Entrance exam problem set. – GG2012 Oct 05 '12 at 17:01

3 Answers3

1

This problem can be solved using Dynamic Programming. Let's say your input is array a you can create an array S of the same length. Following is the recurrence relation for the problem.

S[i] = S[i-1] + a[i] > a[i] ? S[i-1] + a[i] : a[i]

Base case: S[0] = a[0]

Keep a max to track maximum sum. Finally return the max.

Amol
  • 85
  • 2
  • 4
0

Answer is http://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane.27s_algorithm

The idea behind this algorithm is that we assume we know the true maximal subarray of the problem for an array of length N, AND we know the maximal subarray which starts at either end. (rationale: If we assume we know the maximal sequences which touch the ends, and we gradually tack on more elements to the end, then we cannot miss the true maximal subarray since at some point the element added to the end will be the same element as the endpoint of the true maximal subarray.) Tacking on an extra element might increase the length of the longest subarray attached to the end. If the subarray's sum goes below 0, we reset it. If it goes above our current best candidate solution for the true maximal subarray, we replace our best candidate solution.

Alternatively, we can use the power of integration. (It's an O(N) pass you can do for free; you can also differentiate for free.) Then we look at all the extrema, searching for the two extrema MIN and MAX, such that MAX is to the right of MIN (or else you'd be finding the most negative sum), and also such that MAX-MIN (the consecutive sum) is greatest. You could brute-force this subproblem (and still be O(N) if the number of extreme number less than sqrt(N)), or you can solve it in a more efficient manner [could use some help here].

ninjagecko
  • 88,546
  • 24
  • 137
  • 145
-3

This is the seqeuence of all non-negative elements which is easy to find in linear O(n) time.

kelsar
  • 108
  • 5