# 53. Maximum Subarray & 918. Maximum Sum Circular Subarray

[ **53. Maximum Subarray**](https://leetcode.com/problems/maximum-subarray/submissions/1)

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.

***My Solutions:***

 在每一步维护两个变量，一个是全局最优，就是到当前元素为止最优的解。一个是局部最优，就是必须包含当前元素的最优解

方法1：dp，留住当前数字最大的可能性，可以用dp【】储存（见comment out部分）

Time: O(n); Space: O(n)

优化1: 优化一下用int temp储存局部最大值，用int max储存全局最大值。

Time: 不变；Space: O(1)

<pre><code>class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length &#x3C;= 0) {
            return 0;
        }
        
// 方法1        
//         int n = nums.length;
//         int[] dp = new int[n]; // dp[i] means the maximum subarray ending with nums[i] 
//         dp[0] = nums[0];
//         int max = dp[0];
        
//         for(int i = 1; i &#x3C; n; i++){
//             // dp[i]是包含当前位置的最优解
//             dp[i] = Math.max(nums[i] + dp[i - 1] , nums[i]);
//             max = Math.max(max, dp[i]);
//         }   
//         return max;

<strong>        // 优化1.1
</strong>        int max = nums[0];
        int temp = nums[0];
        for (int i = 1; i &#x3C; nums.length; i++) {
            // temp records the max of (curr element + subarray before curr element) OR current element so far
            temp = Math.max(temp + nums[i], nums[i]); //局部最佳 
            max = Math.max(temp, max); //全局最佳
        }
        return max;
        
        // 优化1.2
        int max = Integer.MIN_VALUE, temp = 0;
        for (int n : nums) {
            if (n + temp > n) temp += n; // temp + n 是最优解
            else temp = n; // 只有n是最优解
            max = Math.max(max, temp); // max records the largest subarray
        }
        return max;
        
    // e.g. [5,4,-1,7] 
    // at i = 0, temp = 5, max = 5
    // at i = 1, temp = 9, max = 9
    // at i = 2, temp = 8, max = 9
    // at i = 3, temp = 15, max = 15
    }
}
</code></pre>

**918.Maxium Sum Circular Subarray**

和#53类似，但是可以首尾相连。

**Example 2:**

<pre><code><strong>Input: nums = [5,-3,5]
</strong><strong>Output: 10
</strong><strong>Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10.
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: nums = [-3,-2,-3]
</strong><strong>Output: -2
</strong><strong>Explanation: Subarray [-2] has maximum sum -2.
</strong></code></pre>

***My Solutions:***

因为首尾相连，结果可能有两种情况：

* 最大子数组是原数组的子数组或本身 --> 和#53题一样
* 最大子数组是由原数组的前缀子数组以及后缀子数组组合而成 --> 换一个思路，可以在原数组中找到一个最小子串和，然后再使用原数组的总和减去这个最小子串和，即可得到一个最大的环形子串。找到最小子串和的逻辑和最大子串和的方法相反

方法1:

```
public int maxSubarraySumCircular(int[] nums) {
    // case 1
    int max = Integer.MIN_VALUE, temp = 0;
    for (int n : nums) {
        // sum records the current element OR (curr element + subarray) so far
        if (temp + n > n) temp += n; 
        else temp = n;
        max = Math.max(max, temp);
    }

    // case 2
    temp = 0; 
    int sum = 0, min = Integer.MAX_VALUE;
    for (int n : nums) {
        sum += n;
        if (temp + n > n) temp = n; 
        else temp += n;
        min = Math.min(min, temp);
    }

    if (min == allSum) return max; // if all numbers are negative
    return Math.max(max, sum - min);
}
```

优化1: 观察一下，其实两次遍历可以减少至一次，因为每次都在重新计算temp。注意这里的max和min是第一个数字。

```
    int sum = 0, max = nums[0], currMax = 0, min = nums[0], currMin = 0;
    for (int n : nums) {
        sum += n;
        currMax = Math.max(currMax, 0) + n;
        max = Math.max(max, currMax);
        currMin = Math.min(currMin, 0) + n;
        min = Math.min(min, currMin);
    }
    return sum == min ? max : Math.max(max, sum - min);
```