题解 | #环形数组的连续子数组最大和#

要求最大连续子数列，只可能有两种情况：一是不过环，二是要过环(当数组长度>2)。那么就将两种情况的最大值分别求出来，再进行比较取最大值。

其中，第一种不过环的好求，就是普通数组的连续子数组最大值；

对于第二种过环的，我们要知道：在一个数组中除去头尾后，取一个不过环的连续子数列，剩余部分便是一个过环的连续子数列。数组元素总和固定，只要取的不过环的子数列之和最小，剩余过环的子数列之和就最大。

#include <algorithm>
#include <cstdint>
#include <cstdio>
using namespace std;
int main() {
    int n, dp_max[100010], dp_min[100010];
    int maxt = INT32_MIN, mint = INT32_MAX, sum = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int t;
        scanf("%d", &t);
        if (!i) //dp_max初始条件
            dp_max[0] = t;
        else {
            dp_max[i] = max(dp_max[i - 1] + t, t);
            if (i == 1) //dp_min初始条件，去除头a[0]
                dp_min[1] = t;
            else if (i != n - 1) //dp_min要去除尾
                dp_min[i] = min(dp_min[i - 1] + t, t);
        }
        maxt = dp_max[i] > maxt ? dp_max[i] : maxt;
        //dp_min去除头和尾
        if (i != 0 && i != n - 1)
            mint = dp_min[i] < mint ? dp_min[i] : mint;
        sum += t;
    }
    int res;
    if(n>2)
        res= max(maxt, sum - mint);
    else
        res=maxt;
        printf("%d",res);
    return 0;
}
// 64 位输出请用 printf("%lld")