Leetcode 918. 环形子数组的最大和

Leetcode

发布日期: 2023-09-03

更新日期: 2023-09-03

文章字数: 857

阅读时长: 3 分

阅读次数:

Leetcode 918. 环形子数组的最大和

概要：子数组的最大和利用的是动态规划/滑动窗口的思想，对于环形子数组，需要考虑的是前后元素之间的大小关系，比如[1,2,3,-4]，在环形数组中即为：[1,2,3,-4,1,2,3,-4…],我们要利用动态规划，找到区间子数组最小值和最大值，分别进行判断操作。

1. 题目说明

给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。
环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。
子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], ..., nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。

示例 1：

输入：nums = [1,-2,3,-2]
输出：3
解释：从子数组 [3] 得到最大和 3

2. 解答分析

首先需要明确的是：环形子数组的最大和包含两种可能性，一是直接动态规划得到子数组的最大和MaxF，二是环形子数组的出现循环，此时需要将元素之和sum减去子数组中的区间最小值minS后的值同MaxS进行比较.
- 具体而言：由于是循环数组，我们可以选择将某一个区间剔除，计算剩余部分的最大子数组和。剔除的区间就是使得 minS取最小值的那个区间。
- 如果我们将剔除的区间放在数组的开头或结尾，那么剩余的部分即包含了原始数组的循环部分。
  
  因此，sum - minS 就代表了考虑循环的情况下，剔除特定区间后剩余部分的最大子数组和。
动态规划包含了对于数组元素的选或不选的问题，这里直接遍历即可.

3. 具体代码

该算法使用了动态规划的思想。通过遍历数组nums，维护以下变量：
- maxS：最大子数组和，初值设为负无穷大。
- minS：最小子数组和，初值设为0（因为可以为空数组）。
- maxF：以当前元素为结尾的最大子数组和。
- minF：以当前元素为结尾的最小子数组和。
- sum：数组nums的总和。
代码如下：

class Solution{
    public int maxSubarraySumCircular(int[] nums){
        int maxS = Integer.MIN_VALUE; // 最大子数组和，不能为空
        int minS = 0; // 最小子数组和，可以为空
        int maxF = 0, minF = 0, sum = 0;
        for (int x : nums) {
            // 以 nums[i-1] 结尾的子数组选或不选（取 max）+ x = 以 x 结尾的最大子数组和
            maxF = Math.max(maxF, 0) + x;
            maxS = Math.max(maxS, maxF);
            // 以 nums[i-1] 结尾的子数组选或不选（取 min）+ x = 以 x 结尾的最小子数组和
            minF = Math.min(minF, 0) + x;
            minS = Math.min(minS, minF);
            sum += x;
        }
        return sum == minS ? maxS : Math.max(maxS, sum - minS);
    }
}