【Kadane】Leetcode 918. 环形子数组的最大和【中等】

环形子数组的最大和

给定一个长度为 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

解题思路

要找到环形数组的最大子数组和，分为两种情况进行考虑：

子数组不跨越数组的末尾和开头：这种情况可以通过经典的Kadane算法求解，
Kadane算法可以在O(n)时间复杂度内找到数组中的最大子数组和。

子数组跨越数组的末尾和开头： 这种情况可以转换为一个求解问题，
即数组中的最小子数组和，然后用总和减去最小子数组和得到最大子数组和。
在这里插入图片描述

Java实现

public class MaxCircularSubarraySum {public int maxSubarraySumCircular(int[] nums) {// 计算不跨越数组末尾和开头的最大子数组和int maxKadane = kadane(nums);// 计算数组的总和int totalSum = 0;for (int num : nums) {totalSum += num;}// 计算最小子数组和int minKadane = kadaneMin(nums);// 如果数组中的所有元素都是负数，则返回 Kadane 算法的结果if (totalSum == minKadane) {return maxKadane;} else {return Math.max(maxKadane, totalSum - minKadane);}}// Kadane 算法，计算最大子数组和private int kadane(int[] nums) {//记录以当前元素结尾的最大子数组和int maxEndingHere = nums[0];//记录到目前为止找到的最大子数组和int maxSoFar = nums[0];for (int i = 1; i < nums.length; i++) {maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);maxSoFar = Math.max(maxSoFar, maxEndingHere);}return maxSoFar;}// 计算最小子数组和private int kadaneMin(int[] nums) {//记录以当前元素结尾的最大子数组和,记录到目前为止找到的最小子数组和int minEndingHere = nums[0], minSoFar = nums[0];for (int i = 1; i < nums.length; i++) {minEndingHere = Math.min(nums[i], minEndingHere + nums[i]);minSoFar = Math.min(minSoFar, minEndingHere);}return minSoFar;}// 测试用例public static void main(String[] args) {MaxCircularSubarraySum solution = new MaxCircularSubarraySum();int[] nums1 = {1, -2, 3, -2};int[] nums2 = {5, -9, 4, 4,-9,5};int[] nums3 = {3, -1, 2, -1};int[] nums4 = {3, -2, 2, -3};int[] nums5 = {-2, -3, -1};System.out.println(solution.maxSubarraySumCircular(nums1)); // 期望输出: 3System.out.println(solution.maxSubarraySumCircular(nums2)); // 期望输出: 10System.out.println(solution.maxSubarraySumCircular(nums3)); // 期望输出: 4System.out.println(solution.maxSubarraySumCircular(nums4)); // 期望输出: 3System.out.println(solution.maxSubarraySumCircular(nums5)); // 期望输出: -1}
}