AlgoPressAppearance
0918-环形子数组的最大和
https://leetcode.cn/problems/maximum-sum-circular-subarray
给定一个由整数数组 A表示的环形数组 C，求 C的非空子数组的最大可能和。
在此处，环形数组意味着数组的末端将会与开头相连呈环状。（形式上，当0 <= i < A.length时C[i] = A[i]，且当i >= 0时C[i+A.length] = C[i]）
此外，子数组最多只能包含固定缓冲区 A中的每个元素一次。（形式上，对于子数组C[i], C[i+1], ..., C[j]，不存在i <= k1, k2 <= j其中k1 % A.length= k2 % A.length）
示例 1：
输入：[1,-2,3,-2]
输出：3
解释：从子数组 [3] 得到最大和 3
示例 2：
输入：[5,-3,5]
输出：10
解释：从子数组 [5,5] 得到最大和 5 + 5 = 10
示例 3：
输入：[3,-1,2,-1]
输出：4
解释：从子数组 [2,-1,3] 得到最大和 2 + (-1) + 3 = 4
示例 4：
输入：[3,-2,2,-3]
输出：3
解释：从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3
示例 5：
输入：[-2,-3,-1]
输出：-1
解释：从子数组 [-1] 得到最大和 -1
提示：
-30000 <= A[i] <= 30000
1 <= A.length <= 30000
思路分析
如果不考虑环形数组，那么就是 动态规划 求子序列的最大和。 环形数组表示首尾相连，在从0-n循环n次计算子序列的最大值，最后取出最大和。 此方法时间复杂度 O(n^n) ，会超时，参考如下
csharp
//注意：会超时
public class Solution {
private int MaxSubArray(int[] nums, int start, int end){
int[] dp = new int[nums.Length];
int maxSum = nums[start];
dp[start] = nums[start];
for(int i = start+1; i<end; i++){
dp[i] = Math.Max(dp[i-1]+nums[i],nums[i]);
if(maxSum < dp[i]){
maxSum = dp[i];
}
}
return maxSum;
}
public int MaxSubarraySumCircular(int[] nums) {
//合并两个数组
int[] nums2 = new int[nums.Length * 2];
for(int i=0;i<nums.Length;i++){
nums2[i] = nums[i];
nums2[i+nums.Length] = nums[i];
}
//从开始求
int maxSum = nums[0];
for(int i=0; i<nums.Length; i++){
int sum = MaxSubArray(nums2, i, i+nums.Length);
if(maxSum < sum){
maxSum = sum;
}
}
return maxSum;
}
}
思路2 ： 配合最小子序和
前置知识 最大子序和。 会了最大子序和，这题也就明白了。 对于环形数组，分两种情况。 (1)答案在数组中间，就是最大子序和。例如[1,-2,3,-2]； (2)答案在数组两边，例如[5,-3,5]最大的子序和就等于数组的总和SUM-最小的子序和。(一种特殊情况是数组全为负数，也就是SUM-最小子序和==0，最大子序和等于数组中最大的那个)。
csharp
public class Solution{
public int MaxSubarraySumCircular(int[] nums){
if(nums.Length == 1){
return nums[0];
}
int[] dpMax = new int[nums.Length];
int[] dpMin = new int[nums.Length];
int maxSum = nums[0]; //最大子序和
int minSum = nums[0]; //最小子序和
int maxValue = nums[0]; //最大值
int sum = nums[0];
for(int i=1; i < nums.Length; i++){
dpMax[i] = Math.Max(dpMax[i-1] + nums[i], nums[i]);
dpMin[i] = Math.Min(dpMin[i-1] + nums[i], nums[i]);
if(maxSum < dpMax[i]){
maxSum = dpMax[i];
}
if(minSum > dpMin[i]){
minSum = dpMin[i];
}
sum += nums[i];
if(maxValue < nums[i]){
maxValue = nums[i];
}
}
if(sum - minSum == 0){
return Math.Max(maxSum,maxValue);
}
else{
return Math.Max(maxSum, sum - minSum);
}
}
}
官方解法【TODO】
Kadane 算法
kadane算法是在动态规划解的基础上进一步优化。 它使用一根指针保存以i为结尾的子数组最大值之和，使用另一根指针保存迄今为止的子数组最大值之和。 算法时间复杂度为O（n）,空间复杂度为O(1)。代码非常漂亮优雅。
python
def maxSubArrayKadane(nums):
length = len(nums)
max_ending_here = max_sub_sum = nums[0]
for i in range(1,length):
max_ending_here = max(max_ending_here+nums[i],nums[i])
max_sub_sum = max(max_ending_here, max_sub_sum)
return max_sub_sum
csharp
public class Solution{
public int MaxSubArray(int[] nums){
int maxSum = nums[0];
int maxEndingHere = nums[0];
for(int i=1;i<nums.Length;i++){
maxEndingHere= Math.Max(maxEndingHere+nums[i],nums[i]);
maxSum = Math.Max(maxEndingHere,maxSum);
}
return maxSum;
}
}
复习:20220520
当最大连续和在数组中间的时候，那么就和正常的最大连续和的计算方法一样。 当最大连续和不在数组中间的时候， 那么 index=0 和 index=nums.Length-1 这两个数必须是被选中的，否则他就是第一种情况。 现在我们要求首位的数组加起来最大，那么就要求中间的数加起来最小，这样 sum - 中间最小，就是两边最大的结果。
csharp
public class Solution {
public int MaxSubarraySumCircular(int[] nums) {
int sum = nums[0];
int max = nums[0];
int curSum = nums[0];
int min = 0;
//求最大连续和
for(int i=1; i<nums.Length; i++){
sum+=nums[i]; //求和
curSum = Math.Max(curSum+nums[i],nums[i]);
max = Math.Max(max,curSum);
}
//求最小连续和
curSum = 0;
for(int i=1; i<nums.Length-1; i++){
curSum = Math.Min(curSum+nums[i],nums[i]);
min = Math.Min(curSum,min);
}
return Math.Max(max,sum-min);
}
}