Maximum Subarray

Question: Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

You may view the full question here. And I borrowed some ideas from this wonderful site for the following approach.

Approach 1: This is a fairly simple approach with a time complexity of O(n). The approach can be attributed to the one core principle that one ought NOT to spend more than what one can.

Oh, let me cut to the chase — say you have an array such as [2, -3, 4]. Isn’t it tempting to consider the prospect of adding all three numbers to possibly find the maximum sum? Let’s do exactly that then —

Step 1: Just select the first element — 2

Step 2: Now consider the sum of the first two elements — 2+(-3) = -1

Step 3: Now add all the three elements — 2+(-3)+4 = (-1) + 4 = 3

Ouch! See what just happened there? As soon as you encounter a negative sum, as in step 2; it ought to be a red flag. It just doesn’t make sense to carry forward a part of the array that gives a negative sum.

To generalize the idea let’s assume the max sum array is built of two sub arrays A and B. Let’s once again consider the previous example — [2,-3, 4].

Should we include 2 in the final sum array? Let 2 be the element that composes the sub array A, and let B be the prospective elements of the remaining part of the max sum array. Clearly, sub-array A increases the value of sub-array B by the value of 2, and therefore, increases the value of the max sum array as a whole.

Next, should -3 be included too? We currently have A = [2]. Let’s append the element -3 to A, so new A = [2, -3]. The net value of A is now -1. Clearly, no matter what the value of B is, by including the elements in A, we are only reducing the net worth of the max array by 1. On the other hand, considering B as it is, would have given us a larger sum value to work with. In code, this establishes the logic behind re-initializing the sum array, whenever we encounter a negative sum.

Now, for the last bit. Just like a typical max value code implementation, we store the max sum value so far encountered in a temporary variable and return it in the end.

//Approach 1
//Runtime: 6ms
//Memory usage: 39.6MB
public int maxSubArray(int[] nums) {
        int max = nums[0];
        int currSum = nums[0];
        for(int i = 1;i<nums.length; i++){
            if(currSum<0){
                currSum = nums[i];
            } else {
                currSum+=nums[i];
            }
            max = Math.max(max, currSum);
        }
        return max;
    }

In case you’d like to see a Dynamic Programming version, a probable starting point from which this solution was derived, you may take a peek at this post.

Ta-Da! That’s all for today folks. See you soon with a better implementation and/or a different problem! Until then…

Find more posts here.

Cheers & Chao!