53. Maximum Subarray & 918. Maximum Sum Circular Subarray

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

My Solutions:

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

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

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

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

Time: 不变；Space: O(1)

class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length <= 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 < n; i++){
//             // dp[i]是包含当前位置的最优解
//             dp[i] = Math.max(nums[i] + dp[i - 1] , nums[i]);
//             max = Math.max(max, dp[i]);
//         }   
//         return max;

        // 优化1.1
        int max = nums[0];
        int temp = nums[0];
        for (int i = 1; i < 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
    }
}

918.Maxium Sum Circular Subarray

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

Example 2:

Input: nums = [5,-3,5]
Output: 10
Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10.

Example 3:

Input: nums = [-3,-2,-3]
Output: -2
Explanation: Subarray [-2] has maximum sum -2.

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);