C++程序最大循环子数组和

什么是最大循环子数组和？

最大循环子数组和是指在一个循环数组中找到连续的一段子数组，使得子数组内的所有元素的和最大。循环数组是指数组的首尾相接，即最后一个元素的下一个元素是数组的第一个元素。

比如说，在数组 [2,-1,3,-2,-3,4,1] 中，最大循环子数组和为 [3,-2,-3,4]，它们的和为 2。

解决方法

我们可以使用 Kadane 算法来解决这个问题。Kadane 算法是一种动态规划算法，通过遍历整个数组，计算所有可能的子数组和，找出最大的子数组和。

但在这个问题中，由于数组是循环的，我们需要对 Kadane 算法进行一些修改。

首先，我们需要计算出数组的总和 sum，然后，我们可以运用 Kadane 算法来找到最大的子数组和。此时，如果最大的子数组和小于0，我们就可以直接返回 sum。

然后，我们可以将数组的每个元素取反，再运用 Kadane 算法来找到最小的子数组和。此时，如果最小的子数组和大于等于0，我们也可以直接返回 sum。

最后，我们只需要将数组的总和 sum 和 Kadane 算法找到的最大的子数组和与最小的子数组和之和，取最大值即为所求的最大循环子数组和。

Let’s see the code:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int kadane(vector<int>& nums) {
    int max_sum = INT_MIN, sum = 0;
    for (int i = 0; i < nums.size(); i++) {
        sum = max(nums[i], sum + nums[i]);
        max_sum = max(max_sum, sum);
    }
    return max_sum;
}

int maxCircularSubarraySum(vector<int>& nums) {
    int sum = 0, max_sum = 0, min_sum = 0;
    for (int i = 0; i < nums.size(); i++) {
        sum += nums[i];
        nums[i] = -nums[i];
    }
    max_sum = kadane(nums);
    for (int i = 0; i < nums.size(); i++) {
        nums[i] = -nums[i];
    }
    min_sum = kadane(nums);
    if (min_sum >= 0) return max_sum;
    return max(max_sum, sum + min_sum);
}

int main() {
    vector<int> nums = {2, -1, 3, -2, -3, 4, 1};
    int res = maxCircularSubarraySum(nums);
    cout << res << endl;
    return 0;
}

在上面的代码中，我们首先定义了一个函数 kadane，用来计算最大的子数组和。然后，我们定义了一个函数 maxCircularSubarraySum，用来计算最大循环子数组和。

在函数 maxCircularSubarraySum 中，我们首先计算了数组的总和 sum，然后将数组的每个元素取反，运用 Kadane 算法找到了最小的子数组和。最后，我们根据最小的子数组和是否大于等于0来判断是否返回 sum 或者是返回 sum 与 Kadane 算法找到的最大的子数组和与最小的子数组和之和的最大值。