Leetcode 918. Maximum Sum Circular Subarray

[Woodyiiiiiii]

这道题我初始想法是使用滑动窗口，但显然，没有限制条件和移动，没法写出来。

那么这题其实要有点No.53 Maximum Subarray的基础，那道题最简便的方法是使用Kadane's Algorithm求解数组中最大的和的子数组。

这题稍微绕了下弯，因为题目要求是circular array，所以最大的和的子数组有两种模式：

1. 连续子数组
2. 首尾两端不相交的子数组

第一种直接用53题的思路可以求出来，第二种可以用逆向思维，求出最小数组的和然后用总和相减即可。注意如果第二种情况子数组就是数组本身，则说明数组所有元素都是non-positive，那么就不用考虑第二种情况。

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int preMin = 0, preMax = 0, min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        // use Kadane's algorithm to find the max subarray sum and min subarray sum
        for (int num : nums) {
            preMin = Math.min(preMin + num, num);
            min = Math.min(min, preMin);
            preMax = Math.max(preMax + num, num);
            max = Math.max(max, preMax);
        }
        int sum = Arrays.stream(nums).sum();
        return sum == min ? max : Math.max(max, sum - min);
    }
}

**总结kadane算法: **

• kadane算法一般用于求子数组最大值和/乘法的情况
• 一般结构是从左到右遍历，稍微有点贪心和DP的思想，每次用max和min判断目前循环的最值

可以用到kadane's algorithm算法的类似题目：

• 53. Maximum Subarray
• 121. Best Time to Buy and Sell Stock
• 152. Maximum Product Subarray
• 198. House Robber
• 2606. Find the Substring With Maximum Cost (双周赛101，记录最小值使用Kadane)
• 1749. Maximum Absolute Sum of Any Subarray

---

• 918. Maximum Sum Circular Subarray
• 53. Maximum Subarray