# 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;
    }
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://junnie.gitbook.io/nine-chapter/6.array/41maximum-subarray.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.