使用状态压缩，用两个变量来代替数组，将时间复杂度从O（n2）压缩到O（n）

#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    int prev;
    cin >> prev;
    int res = prev;

    while (--n) {
        int a;
        cin >> a;
        prev = max(a, prev + a);
        res = max(prev, res);
    }

    cout << res << endl;
}

int max(int a, int b) {
    return a > b ? a : b;
}