contiguous subarray with largest sum in an array (Maximum Subarray)

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;
    }
};
Advertisements

2 Comments (+add yours?)

  1. nad
    Oct 20, 2012 @ 12:18:47

    This works except it doesn’t return the subarray, only its sum. In any case, thanks for this blog. It’s very helpful.

    Reply

    • Runhe Tian
      Oct 20, 2012 @ 17:16:47

      Hi 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.

      Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: