[algogeeks] Re: Given an array containing both positive and negative integers, we r required to find the sub-array with the largest sum
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
[algogeeks] Re: Given an array containing both positive and negative integers, we r required to find the sub-array with the largest sum
Think of the negative numbers as consumers from a warehouse and positive numbers as producers from the warehouse. The problem reduces to plotting the inventory (starting from time = 0 to time = n) and then finding the max amplitude over time axis in +ve quadrant of the inventory profile which can be done in O(n).