Description

LeetCode 53

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.

Analysis

  1. Divide and Conquer

Get the middle elemnt of the array. Then it is easy to find the maximum subarray that contains the middle element, just expand the subarray to both sides. And do the same things for the subarray that is left or right to the middle element recursively. Find the maximum sum of the sum that contains the middle element, the sum that is left to the middle element and the sum that is right to the middle element. The time is \(O(logn)\).

2. Dynamic Programming

The optimal substructure is the maximum subarray that contains the last element.

Define \(d[i]\) as the maximum subarray’s sum that contains \(nums[i]\), then

$$d[i]=max(nums[i],nums[i]+d[i-1])$$

Find the maximum of \(d[1…n]\) and return it.

The time and space are both \(O(n)\).

The state transition equation just uses the information of last state. So we can use one variable instead of an array. The space will be \(O(1)\).

Solution

//Dynamic Programming O(n)
class Solution {
    public int maxSubArray(int[] nums) {
        if (nums==null||nums.length==0) return 0;
        int res=nums[0];
        int sum=nums[0];
        for(int i=1;i<nums.length;i++)
        {
            sum=Math.max(nums[i],sum+nums[i]);
            res=Math.max(res,sum);
        }
        return res;
    }
}

//Divide and Conquer O(nlogn)
class Solution {
    public int maxSubArray(int[] nums) {
        if (nums==null||nums.length==0) return 0;
        return helper(nums,0,nums.length-1);
    }
    public int helper(int[] nums,int low,int high)
    {
        if(low>high) return Integer.MIN_VALUE;
        if(low==high) return nums[low];
        int mid=(low+high)/2;
        int midsum,leftsum,rightsum;
        int i=mid;
        int j=mid;
        int maxmidleftsum=Integer.MIN_VALUE,maxmidrightsum=Integer.MIN_VALUE;
        int midleftsum=0,midrightsum=0;
        while(i>=low)
        {
            midleftsum=midleftsum+nums[i];
            maxmidleftsum=Math.max(maxmidleftsum,midleftsum);
            i=i-1;
        }
        while(j<=high)
        {
            midrightsum=midrightsum+nums[j];
            maxmidrightsum=Math.max(maxmidrightsum,midrightsum);
            j=j+1;
        }
        midsum=maxmidleftsum+maxmidrightsum-nums[mid];
        leftsum=helper(nums,low,mid-1);
        rightsum=helper(nums,mid+1,high);
        if(midsum>=leftsum&&midsum>=rightsum) return midsum;
        else if(leftsum>=midsum&&leftsum>=rightsum) return leftsum;
        else return rightsum;
    }
}

Reference

[1] https://github.com/EdwardShi92/Leetcode-Solution-Code/blob/master/MaximumSubarray.java

[2] Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms. MIT press.

Leave a Reply

Your email address will not be published. Required fields are marked *