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.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.


class Solution {
    public int maxSubArray(int[] nums) {
        
    }
}

Problem Clarification

We need to consider sum of contiguous elements.

Idea - 1

Try each of O(n^2) subarray and keep track of the max sum. Time O(n^2), space O(1). 

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int maxsum = Integer.MIN_VALUE;
        
        for(int i = 0; i < n; ++i)
        {
            int sum = 0;
            for(int j = i; j < n; ++j)
            {
                sum += nums[j];
                maxsum = Math.max(maxsum, sum);
            }
        }
        
        return maxsum;
    }
}


Runtime: 105 ms, faster than 5.03% of Java online submissions for Maximum Subarray.
Memory Usage: 49.3 MB, less than 5.05% of Java online submissions for Maximum Subarray.

Idea - 2

While considering if we should include a_i to the running sum, if the sum of a_0,\ a_1,\ \ldots\,\ a_{i-1} does not help a_i then we start a fresh run starting at a_i. The algorithm has time O(n) and space O(1). 

class Solution {
    public int maxSubArray(int[] nums) {
        int maxsum = Integer.MIN_VALUE;
        int sum = 0;
        for(int i = 0; i < nums.length; ++i)
        {
            sum = Math.max(sum+nums[i], nums[i]);
            maxsum = Math.max(maxsum, sum);
        }
        
        return maxsum;
    }
}


Runtime: 1 ms, faster than 97.15% of Java online submissions for Maximum Subarray.
Memory Usage: 38.4 MB, less than 92.18% of Java online submissions for Maximum Subarray.

Idea - 3

If we break the array in middle and find solutions: one to the left and other to the right, then the global solution would be the maximum among these two solutions and the solution that cross boundary. Time O(n\lg{n}) and stack space O(\lg{n}). 

class Solution {
    public int maxSubArray(int[] nums) {
        return maxSum(nums, 0, nums.length-1);
    }
    
    private int maxSum(int[] A, int lo, int hi)
    {
        if(lo > hi)
        {
            return 0;
        }
        
        if(lo == hi)
        {
            return A[lo];
        }
        
        int mid = lo+(hi-lo)/2;
        
        int leftSum = maxSum(A, lo, mid);
        int rightSum = maxSum(A, mid+1, hi);
        
        // last element to the left and first element
        // to the right must be in the crossing solution
        //
        int middleSum = mid+1 > hi ? 0 : A[mid+1];
        middleSum += A[mid];
        
        // can we increase going to the right
        //
        int sum = middleSum;
        for(int j = mid+2; j <= hi; ++j)
        {
            sum += A[j];
            middleSum = Math.max(middleSum, sum);
        }
        
        // can we increase going to the left
        //
        sum = middleSum;
        for(int j = mid-1; j >= lo; --j)
        {
            sum += A[j];
            middleSum = Math.max(middleSum, sum);
        }
        
        return Math.max( middleSum, Math.max(leftSum, rightSum) );
    }
}


Runtime: 3 ms, faster than 74.42% of Java online submissions for Maximum Subarray.
Memory Usage: 38.5 MB, less than 92.00% of Java online submissions for Maximum Subarray.

Leave a comment