使用状态压缩，用两个变量来代替数组，将时间复杂度从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;
}

C++ :

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,s=0,b[110]={0},max=INT_MIN;
    cin>>n;
    int a[110];
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        s=s+a[i];
        b[i]=s;
    }
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n-i+1;j++)
        {
            if (b[j+i-1]-b[j-1]>max) max=b[j+i-1]-b[j-1];
        }
    }
    cout<<max<<endl;
    return 0;
}