41.Maximum Subarray

1.Description(Easy)

Given an array of integers, find a contiguous subarray which has the largest sum.

Notice

The subarray should contain at least one number.

Example

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

Challenge

Can you do it in time complexity O(n)?

2.Code

Version 1：Greedy O(n)

O(n)就是一维DP.

假设A(0, i)区间存在k，使得[k, i]区间是以i结尾区间的最大值， 定义为Max[i], 在这里，当求取Max[i+1]时，Max[i+1] = Max[i] + A[i+1], if (Max[i] + A[i+1] >0)= 0, if(Max[i]+A[i+1] <0)，如果和小于零，A[i+1]必为负数，没必要保留，舍弃掉然后从左往右扫描，求取Max数字的最大值即为所求。

 public int maxSubArray(int[] nums) {
        if(nums==null || nums.length==0){
            return 0;
        }

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

Version 2: Prefix Sum(基本所有的subarray的问题都跟prefix有关) O(n)

找到一个最小的prefix sum和一个最大的差值

 public int maxSubArray2(int[] nums){
        if(nums==null || nums.length==0){
            return 0;
        }
        int max=Integer.MIN_VALUE;
        int sum=0;
        int minPrefix=0;
        for(int i=0;i<nums.length;i++){
            sum=sum+nums[i];
            max=Math.max(max, sum-minPrefix);
            minPrefix=Math.min(minPrefix, sum);
        }
        return max;
    }

Version 3: O(logn)

但是题目中要求，不要用这个O(n)解法，而是采用Divide &Conquer。这就暗示了，解法必然是二分。分析如下：

假设数组A[left, right]存在最大值区间[i, j](i>=left & j<=right)，以mid = (left + right)/2 分界，无非以下三种情况：

subarray A[i,..j] is

(1) Entirely in A[low,mid-1]

(2) Entirely in A[mid+1,high]

(3) Across mid

对于(1) and (2)，直接递归求解即可，对于(3)，则需要以min为中心，向左及向右扫描求最大值，意味着在A[left, Mid]区间中找出A[i..mid], 而在A[mid+1, right]中找出A[mid+1..j]，两者加和即为(3)的解。

public int maxSubArray(int[] nums) {
        return binarysearch(nums, 0, nums.length-1, Integer.MIN_VALUE);
    }

    public int binarysearch(int[] nums, int left, int right, int maxValue) {
        if (left > right) return Integer.MIN_VALUE;
        int mid = (left + right) / 2;
        int lmax = binarysearch(nums, left, mid-1, maxValue);
        int rmax = binarysearch(nums, mid+1, right, maxValue);
        maxValue = Math.max(maxValue, Math.max(lmax,rmax));

        int lsum = 0; int mlmax = 0;
        for (int i = mid-1; i >= left; --i) {
            lsum += nums[i];
            mlmax = Math.max(mlmax, lsum);
        }

        int rsum = 0; int mrmax = 0;
        for (int i = mid+1; i <= right; ++i) {
            rsum += nums[i];
            mrmax = Math.max(mrmax, rsum);
        }

        maxValue = Math.max(maxValue, mlmax + mrmax + nums[mid]);
        return maxValue;
    }