Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],

the contiguous subarray [4,−1,2,1] has the largest sum = 6.

**Thoughts:**

For each element in the array, we want to track the subarray with the largest sum ending here. And the largest of those largest sums is the result we need. So how do we track the largest sum ending at a particular position? We can keep adding up positive numbers. We can also add negative numbers as long as the sum would be less than 0. If it’s smaller than 0, we need to reset from this position by starting the sum from 0. In the above example, the largest sums ending at each position are [-2,1,-3,4,3,5,6,1,5]. Hence the largest sum is 6.

**code (Java):**

public class Solution {
public int maxSubArray(int[] A) {
int maxSumSoFar = Integer.MIN_VALUE;
int maxSumEndingHere = 0;
for(int num : A) {
maxSumEndingHere = Math.max(maxSumEndingHere + num, num);
maxSumSoFar = Math.max(maxSumSoFar, maxSumEndingHere);
}
return maxSumSoFar;
}
}

**Code (C++):**

class Solution {
public:
int maxSubArray(int A[], int n) {
int maxSumSoFar = INT_MIN;
int maxSumEndingHere = 0;
for(int i = 0; i < n; ++i) {
maxSumEndingHere = max(maxSumEndingHere+A[i], A[i]);
maxSumSoFar = max(maxSumSoFar, maxSumEndingHere);
}
return maxSumSoFar;
}
};

### Like this:

Like Loading...

*Related*

nad

Oct 20, 2012@ 12:18:47This works except it doesn’t return the subarray, only its sum. In any case, thanks for this blog. It’s very helpful.

Runhe Tian

Oct 20, 2012@ 17:16:47Hi Nad, the original question on LeetCode does not require to return the whole subarray. Therefore I didn’t include them. You can easily adapt to a version where it does so, by adding some indices.