[algogeeks] Re: Given an array containing both positive and negative integers, we r required to find the sub-array with the largest sum

[srinivas karlapudi]

this is 'Maximum Subsequence Problem'
i saw solutions of orders of n(3),n(2),nlongn,n
in DataStructures and Algo. Analysis by Mark Allen Weiss.

srinivas

On 1/25/06, Hemanth <[EMAIL PROTECTED]> wrote:

Well,

Here's a solution :
Create an array of cumulative sums i.e. cs[i]  = sum of elements from
index 0 to i

Now, find the maximum cumulative sum index say 'y'. We can exclude
elements after index 'y' since they do not contribute positively to the
cumulative sum.

Also, let 'x' be the minimum cumulative sum point. Then we can ignore
numbers from 0 to x (inlcuding x) since they do not contribute to the
cumulative sum.

So, the indices of the sub-array with the maximal sum should be (x+1,
y)

Thanks,
Hemanth