leetcode每日一题7.20kandane

题目链接：https://leetcode.cn/problems/maximum-sum-circular-subarray/
leetcode今天的题目是一个环形数组求最大和

很明显是一个动态规划，使用kandane算法很简单解决

kandane算法

讲解：https://medium.com/@rsinghal757/kadanes-algorithm-dynamic-programming-how-and-why-does-it-work-3fd8849ed73d
这个大佬讲的比较好
设数组为a时，
当前索引i的最大子数组和等于前索引i-1的最大子数组和加上当前值a[i]

代码实现

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int len = nums.size();
        int local_max = 0;
        int global_max = INT_MIN;

        for (int i = 0; i < 2*len; i++)
        {
            local_max = max(nums[i%len],nums[i%len] + local_max);
            if (local_max > global_max)
                global_max = local_max;
        }
        return global_max;
    }
};

但是这个问题比起其他题目有所不同，是一个环形数组

最大子数组有两种情况

case1

最大子数组和在中间，这时上面的代码就可以直接使用得到最大子数组和

case2

最大子数组贯穿头尾

这时就只能计算最小子数组和，然后用总和减去最小的子数组和即可

最终代码：

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int len = nums.size();
        int local_max = 0;
        int global_max = INT_MIN;
        int total_sum = 0;

        for (int i = 0; i < len; i++) {
            local_max = max(nums[i], nums[i] + local_max);
            global_max = max(local_max, global_max);
            total_sum += nums[i];
        }
        //对于环形的数组，总和一定，总和减去最小的子数组和就是最大子数组和
        int min_wrap = INT_MAX;
        int current_sum = 0;
        for (int i = 0; i < len; ++i) {
            current_sum = min(nums[i], nums[i] + current_sum);
            min_wrap = min(min_wrap, current_sum);
        }
        int max_wrap = total_sum - min_wrap; // 重新计算 max_wrap

        if (max_wrap == 0) {
            return global_max;
        }
        
        return max(global_max, max_wrap);
    }
};