918. 环形子数组的最大和

https://leetcode.cn/problems/maximum-sum-circular-subarray/description/?envType=study-plan-v2&envId=top-interview-150

思路：相比于非环情况，环状的难点是没法找到初始情况，所以就没办法往下推，但是环状的答案分布也有两种，一种是跨越环的分布，另一种是不跨越的（这种情况就是和非环的是一样的），对于跨越的情况可以将环分为两部分（因为数组的和是不变的，所以想找到和最大的子数组和那么对应另一部分肯定就是最小子数组和，最大子数组和（跨越），最小子数组和（不跨越）），所以只要找到不跨越的最小子数组和就行。

上面的最大子数组和和最小子数组和我们都可以通过kadane算法求出（不知道的可以去了解一下，当然用动态规划也是可以的）

class Solution {public int maxSubarraySumCircular(int[] nums) {int n = nums.length;// 采用Kadane算法，计算非环情况的最大子数组和和最小子数组和int currMax = nums[0], currMin = nums[0], sum = nums[0];int globalMax = nums[0], globalMin = nums[0];for(int i = 1; i < n; i++) {currMax = Math.max(nums[i], currMax + nums[i]);currMin = Math.min(nums[i], currMin + nums[i]);globalMax = Math.max(globalMax, currMax);globalMin = Math.min(globalMin, currMin);sum += nums[i];}int ans = 0;// 如果最小子数组和等于整个数组和，说明所有元素都是负数，那么最大子数组和就是全局最大值if(globalMin == sum) {ans = globalMax;return ans;}// 不跨越和跨越的情况里选出较大值ans = Math.max(globalMax, sum - globalMin);return ans;}public static void main(String[] args) {Solution solution = new Solution();int[] nums = {1,-2,3,-2};int ans = solution.maxSubarraySumCircular(nums);System.out.println(ans);}
}