LeetCode_动态规划_中等_918.环形子数组的最大和

心已赠人 2023-10-12 15:32 22阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 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：**  
输入：nums = \[5,-3,5\]  
输出：10  
解释：从子数组 \[5,5\] 得到最大和 5 + 5 = 10

**示例 3：**  
输入：nums = \[3,-2,2,-3\]  
输出：3  
解释：从子数组 \[3\] 和 \[3,-2,2\] 都可以得到最大和 3

**提示：**  
n == nums.length  
1 <= n <= 3 \* 104  
\-3 \* 104 <= nums\[i\] <= 3 \* 104

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/maximum-sum-circular-subarray

## 2.思路 ##

（1）动态规划  
思路参考[该 LeetCode 用户题解][LeetCode]。

相关题目：  
[LeetCode\_动态规划\_简单\_53.最大子数组和][LeetCode_53.]

## 3.代码实现（Java） ##

//思路1————动态规划
    class Solution {
        
        public int maxSubarraySumCircular(int[] nums) {
        
            //数组总和
            int total = 0;
            //最大子数组和
            int maxSum = nums[0];
            //包含当前元素的最大子数组和
            int curMax = 0;
            //最小子数组和
            int minSum = nums[0];
            //包含当前元素的最小子数组和
            int curMin = 0;
            for (int num : nums) {
        
                curMax = Math.max(curMax + num, num);
                maxSum = Math.max(maxSum, curMax);
                curMin = Math.min(curMin + num, num);
                minSum = Math.min(minSum, curMin);
                total += num;
            }
            return maxSum > 0 ? Math.max(maxSum, total - minSum) : maxSum;
        }
    }

[LeetCode]: https://leetcode.cn/problems/maximum-sum-circular-subarray/solution/wo-hua-yi-bian-jiu-kan-dong-de-ti-jie-ni-892u/
[LeetCode_53.]: https://blog.csdn.net/weixin_43004044/article/details/119725240