LeetCode环形子数组的最大和（编号918）
目录
一.题目
二.解题思路
三.解题代码
一.题目
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
提示：
n == nums.length1 <= n <= 3 * 104-3 * 104 <= nums[i] <= 3 * 104
二.解题思路
动态规划解法：
g[i] 表示以i位置为结尾的所有子数组的最小和
环形数组的子数组的最大和有两种情况：
1.拥有最大和的子数组就在数组的中间
2.环形数组的头部和尾部共同组成了拥有最大和的子数组
我们只需要求两种情况的最大值，再确定哪种更大返回即可
对于1：
f[i] 表示以i位置为结尾的所有子数组的最大和
当长度为1时，子数组的最大和为nums[i]
当长度大于1时，子数组的最大和nums[i]+f[i-1]
状态转移方程： f[i]=Math.max(nums[i],f[i-1]);
对于2：
转化为求数组中间的最小子数组和，用数组总和sum-数组中间的最小子数组和(gmin)
同理:
最小和的状态转移方程： g[i]=Math.min(nums[i],g[i-1]);
初始化：可以添加一个虚拟的头部，在状态数组里多开一个空间，填入0
可以使填了0可以使原来的结果不变，f[0]=g[0]=0,
循环填状态方程时就可以直接从1开始，状态数组多加了一个格子，注意下标映射
原数组nums[i]变成nums[i-1]
返回值：注意如果数组全部为负数如 [-1,-2,-3],
那么最大的子数组应该在数组中间，直接返回fmax
三.解题代码
public int maxSubarraySumCircular(int[] nums) {int n=nums.length;int[] f=new int[n+1];int[] g=new int[n+1];int fmax=Integer.MIN_VALUE;int gmin=Integer.MAX_VALUE;int sum=0;for(int i=1;i<=n;i++){sum+=nums[i-1]; //求总数组和f[i] = Math.max(nums[i-1],nums[i-1] + f[i-1]);fmax = Math.max(fmax,f[i]);//求数组中间的最大子数组和g[i] = Math.min(nums[i-1],nums[i-1] + g[i-1]);gmin = Math.min(gmin,g[i]);//求数组中间的最小子数组和} //判断数组是否全为负数，如果是直接返回fmax,不是判断1，2情况哪个大return sum==gmin ? fmax:Math.max(fmax,sum-gmin);}
}