# Maximum Subarray

> 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.

这题最直接的可能就是贪心法。算当前的streak，如果大于0一直加，并一路上记录最大值。一旦streak掉到0以下，就从头来过。因为掉到0一下，前面的数的和就是负担了。

```python
    def maxSubArray(self, nums):

        if len(nums) == 0:
            return 0
        currentSum = 0
        best = nums[0]
        for n in nums:
            currentSum += n
            best = max(currentSum, best)
            if currentSum < 0:
                currentSum = 0

        return best
```

借用prefix 法

```python
    def maxSubArray(self, nums):
        if len(nums) == 0:
            return 0
        prefix = 0
        prefixmin = 0
        best = nums[0]
        for n in nums:
            prefix += n
            best = max(best, prefix - prefixmin)
            prefixmin = min(prefixmin, prefix)

        return best
```

九章上看到一个“有趣”的方法

```java
    public int maxSubArray(int[] nums) {
        // write your code
        if(nums.length == 0){
            return 0; 
        }
        int n = nums.length;
        int[] global = new int[2];
        int[] local = new int[2];
        global[0] = nums[0];
        local[0] = nums[0];
        for(int i = 1; i < n; i ++) {  
            local[i % 2] = Math.max(nums[i], local[(i - 1) % 2] + nums[i]);  
            global[i % 2] = Math.max(local[i % 2], global[(i - 1) % 2]);  
        }  
        return global[(n-1) % 2];  
    }
```

LeetCode 的 discuss 上看到的 DP 的方法

> **Explanation**
>
> Although there’re some other simplified solutions, but DP solution can make the original thought for this problem clearer. In this solution, dp\[i] means the largest sum among the subarrays whose last element is A\[i].
>
> **Solution1. DP Solution - O(n) time, O(n) space**
>
> ```java
> public int maxSubArray(int[] A) {
>     int dp[] = new int[A.length]; int max = A[0]; dp[0] = A[0]; 
>     for (int i = 1; i < A.length; i++) {            
>         dp[i] = Math.max(dp[i-1] + A[i] ,A[i]);
>         max = Math.max(max, dp[i]);
>     }
>     return max;
> }
> ```

LeetCode 的 discuss 上看到的 Divide and conquer 的方法。好复杂

> For each subarray, calculate four attributes:
>
> ```
> mx (largest sum of this subarray), 
> lmx(largest sum starting from the left most element), 
> rmx(largest sum ending with the right most element), 
> sum(the sum of the total subarray).
> ```
>
> The recurrence is: T(n) = 2T(n / 2) + O(1). So the running time of this algorithm is O(n).
>
> ```cpp
> class Solution {
> public:
>     void maxSubArray(vector<int>& nums, int l, int r, int& mx, int& lmx, int& rmx, int& sum) {
>         if (l == r) {
>             mx = lmx = rmx = sum = nums[l];
>         }
>         else {
>             int m = (l + r) / 2;
>             int mx1, lmx1, rmx1, sum1;
>             int mx2, lmx2, rmx2, sum2;
>             maxSubArray(nums, l, m, mx1, lmx1, rmx1, sum1);
>             maxSubArray(nums, m + 1, r, mx2, lmx2, rmx2, sum2);
>             mx = max(max(mx1, mx2), rmx1 + lmx2);
>             lmx = max(lmx1, sum1 + lmx2);
>             rmx = max(rmx2, sum2 + rmx1);
>             sum = sum1 + sum2;
>         }
>     }
>     int maxSubArray(vector<int>& nums) {
>         if (nums.size() == 0) {
>             return 0;
>         }
>         int mx, lmx, rmx, sum;
>         maxSubArray(nums, 0, nums.size() - 1, mx, lmx, rmx, sum);
>         return mx;
>     }
> };
> ```

还有一个叫 Kadane's Algorithm <https://www.youtube.com/watch?v=86CQq3pKSUw>

其实思想和贪心法一样的，只不过做成了DP，好理解一点。dp\[i] 的定义是，sum of the maximum subarray ending at index i.
