[NC]306. 环形子数组的最大和

🚩传送门：牛客题目
力扣题目

题目

给定一个长度为 的环形整数数组 ，返回的非空 子数组 的最大可能和 。

示例 2：

输入：nums = [5,-3,5] 输出：10 解释：从子数组 [5,5] 得到最大和 5 + 5 = 10

解题思路：动态规划

这题一共有两种情况

• 第一种情况：这个子数组不是环状的，就是说首尾不相连。
• 第二种情况：这个子数组一部分在首部，一部分在尾部，我们可以将这第二种情况转换成第一种情况

转化后这题一共有两种情况：比较二者选最大值

• 求连续子数组最大和
• 求连续子数组最小和，再利用_总和-最小和_

解释一下为什么如果是环状情况的 MaxSubarray 中间剩余的红色部分就一定是 MinSubarray 。
我们知道对于数组求连续子数组最小和，一定能求出红色部分，那么剩下的蓝色部分和红色部分是极端对立的，他们的总和 sum 是固定的，红色小了，蓝色就会大，红色达到 MinSubarray 的时候蓝色的部分也就达到了 MaxSubarray ，因此如果是环状蓝色部分一定是最大的。

:::info 💡 至于最终到底是两侧环状和最大，还是中间连续子数组和最大，就需要比较二者了，要注意特殊情况全是负数的情况下，情况一的 MaxSubarray 才是答案 :::

复杂度分析

时间复杂度： ，其中 是数组的长度，只需要遍历数组一次。

空间复杂度： ，常数的空间。

我的代码

public class Main{
    public static void main(String[]args){
        int res_Max=Integer.MIN_VALUE;
        int res_Min=Integer.MAX_VALUE;
        int Max_sum=0;
        int Min_sum=0;
        int sum=0;
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        for(int i=0;i<n;i++){
            // 获取当前数
            int num=sc.nextInt();
            // 计算数组和
            sum+=num;
            // 计算连续最大和
            Max_sum+=num;
            res_Max=(res_Max>Max_sum?res_Max:Max_sum); // 查看能否刷新 
            // 计算连续最小和
            Min_sum+=num;
            res_Min=(res_Min<Min_sum?res_Min:Min_sum);
            if(Max_sum<0) Max_sum=0; // 对正向没贡献
            if(Min_sum>0) Min_sum=0; // 对负向没贡献
        }
        // 正常比较二者的最大值,
        int res=(res_Max>(sum-res_Min))?res_Max:(sum-res_Min);
        // 判断是否是全负数,如果全负数,sum-res_Min==0是个假值,应该选择 res_Max 做答案
        res=(sum==Min_sum?res_Max:res); 
        System.out.println(res);
    }
}