题解 | 最大连续子序列

#include <iostream>
#include<cstring>
using namespace std;

const int MIN = 0xc0c0c0c0;
const int N = 10010;
int f;
int a[N];
int main() {
    int n;
    while (cin >> n) { // 注意 while 处理多个 case
        if (n == 0)break;
        // memset(f,0xc0,sizeof f);
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        //由于要找最左边的端点所以f[i]的定义是以i为左端点的最长连续子序列
        //f[i]=max(f[i+1],0)+a[i]
        //g存放当前序列的右端点
        //right存放最大子序列的右端点
        int res = 0, left = 0, right = 0;
        int g ;
        for (int i = n, f = 0, g = n; i >= 0; i--) {
            //此时f是i+1状态的f
            if (f <= 0) {
                //取等就是为了找到最左边的端点
                f = 0;
                g = i;
            }
            f += a[i];
            if (res < f) {
                //更新最大连续子序列
                res = f;
                left = i;
                right = g;
            }
        }
        printf("%d %d %d\n", res, a[left], a[right]);
    }
}
// 64 位输出请用 printf("%lld")