> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/6.array/41maximum-subarray.md).

# 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**](http://lintcode.com/en/problem/maximum-subarray/#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;
    }
```