算法题环形子数组的最大和-编程实验室

918. 环形子数组的最大和

问题描述

给定一个环形整数数组nums（即数组的末端将会与开头相连），返回非空子数组的最大可能和。

注意：环形数组意味着数组可以首尾相连，因此子数组可以跨越数组的末尾和开头。

示例：

输入: nums = [1,-2,3,-2] 输出: 3 解释: 子数组 [3] 的和最大。 输入: nums = [5,-3,5] 输出: 10 解释: 子数组 [5,5] 的和最大（跨越末尾和开头）。 输入: nums = [-3,-2,-3] 输出: -2 解释: 子数组 [-2] 的和最大。

算法思路

两种情况：

非环形情况：最大子数组完全在数组内部，不跨越边界
- 使用经典的 Kadane 算法
环形情况：最大子数组跨越数组末尾和开头
- 等价于总和减去最小子数组的和
- 跨越边界的子数组 = 整个数组 - 中间的最小子数组

代码实现

方法一：Kadane算法

classSolution{/** * 计算环形数组中非空子数组的最大和 * * @param nums 环形整数数组 * @return 非空子数组的最大可能和 */publicintmaxSubarraySumCircular(int[]nums){// 使用Kadane算法计算最大子数组和intmaxSum=kadaneMax(nums);// 计算数组总和inttotalSum=0;for(intnum:nums){totalSum+=num;}// 使用Kadane算法计算最小子数组和intminSum=kadaneMin(nums);// 特殊情况：如果所有元素都是负数，minSum == totalSum// 此时环形情况会得到 totalSum - minSum = 0，需要非空子数组// 所以直接返回 maxSum（即最大的单个元素）if(totalSum==minSum){returnmaxSum;}// 返回非环形情况和环形情况的最大值returnMath.max(maxSum,totalSum-minSum);}/** * Kadane算法：计算最大子数组和 */privateintkadaneMax(int[]nums){intmaxSoFar=nums[0];intmaxEndingHere=nums[0];for(inti=1;i<nums.length;i++){// 要么扩展之前的子数组，要么重新开始maxEndingHere=Math.max(nums[i],maxEndingHere+nums[i]);maxSoFar=Math.max(maxSoFar,maxEndingHere);}returnmaxSoFar;}/** * Kadane算法变种：计算最小子数组和 */privateintkadaneMin(int[]nums){intminSoFar=nums[0];intminEndingHere=nums[0];for(inti=1;i<nums.length;i++){// 要么扩展之前的子数组，要么重新开始minEndingHere=Math.min(nums[i],minEndingHere+nums[i]);minSoFar=Math.min(minSoFar,minEndingHere);}returnminSoFar;}}

方法二：一次遍历

classSolution{/** * 一次遍历计算最大子数组和、最小子数组和和总和 * * @param nums 环形整数数组 * @return 非空子数组的最大可能和 */publicintmaxSubarraySumCircular(int[]nums){intmaxSum=nums[0];// 最大子数组和intminSum=nums[0];// 最小子数组和intmaxEndingHere=nums[0];// 当前最大子数组和intminEndingHere=nums[0];// 当前最小子数组和inttotalSum=nums[0];// 数组总和for(inti=1;i<nums.length;i++){intnum=nums[i];totalSum+=num;// 更新最大子数组和maxEndingHere=Math.max(num,maxEndingHere+num);maxSum=Math.max(maxSum,maxEndingHere);// 更新最小子数组和minEndingHere=Math.min(num,minEndingHere+num);minSum=Math.min(minSum,minEndingHere);}// 特殊情况处理：所有元素都是负数if(totalSum==minSum){returnmaxSum;}returnMath.max(maxSum,totalSum-minSum);}}

算法分析

时间复杂度：O(n)
- 只需要遍历数组一次或两次
空间复杂度：O(1)
- 只使用常数个额外变量

算法过程

输入：nums = [5,-3,5]

计算非环形最大子数组和：
- [5] = 5,[5,-3] = 2,[5,-3,5] = 7,[-3] = -3,[-3,5] = 2,[5] = 5
- 最大值 = 7
计算总和：5 + (-3) + 5 = 7
计算最小子数组和：
- 最小子数组是[-3]，和为-3
环形最大子数组和 =总和 - 最小子数组和 = 7 - (-3) = 10
最终答案 =max(7, 10) = 10

输入：nums = [-3,-2,-3]

非环形最大子数组和 =-2
总和 =-8
最小子数组和 =-8（整个数组）
由于总和 == 最小子数组和，返回非环形结果-2

测试用例

publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：标准示例int[]nums1={1,-2,3,-2};System.out.println("Test 1: "+solution.maxSubarraySumCircular(nums1));// 3// 测试用例2：环形情况更优int[]nums2={5,-3,5};System.out.println("Test 2: "+solution.maxSubarraySumCircular(nums2));// 10// 测试用例3：全负数int[]nums3={-3,-2,-3};System.out.println("Test 3: "+solution.maxSubarraySumCircular(nums3));// -2// 测试用例4：全正数int[]nums4={1,2,3,4};System.out.println("Test 4: "+solution.maxSubarraySumCircular(nums4));// 10// 测试用例5：单元素int[]nums5={5};System.out.println("Test 5: "+solution.maxSubarraySumCircular(nums5));// 5// 测试用例6：两元素int[]nums6={-2,-3};System.out.println("Test 6: "+solution.maxSubarraySumCircular(nums6));// -2// 测试用例7：复杂环形情况int[]nums7={3,-1,2,-1};System.out.println("Test 7: "+solution.maxSubarraySumCircular(nums7));// 4// 非环形：[3,-1,2] = 4，环形：[2,-1,3] = 4// 测试用例8：另一个复杂情况int[]nums8={3,-2,2,-3};System.out.println("Test 8: "+solution.maxSubarraySumCircular(nums8));// 3// 非环形：[3] = 3，环形：[2,-3,3] = 2// 测试用例9：大数值int[]nums9={10000,-10000,10000};System.out.println("Test 9: "+solution.maxSubarraySumCircular(nums9));// 20000// 测试用例10：交替正负int[]nums10={1,-1,1,-1,1};System.out.println("Test 10: "+solution.maxSubarraySumCircular(nums10));// 3// 环形：[1,-1,1,-1,1] 全部 = 1，或者 [1,1,1] 跨越 = 3}