算法：dp动态规划+贪心

https://www.luogu.com.cn/problem/P1115

dp[i] = max(a[i],dp[i-1]+a[i]);

1.前面正，后面正，保持连接走后者
2.前面正，后面负，保持连接走后者
3.前面负，后面正，重新开始走前者
4.前面负，后面负，重新开始走前者

总结：取决于前面是不是正贡献

#include <bits/stdc++.h>
#define debug(x) cout << '!' << (x) << '!' << endl
#define INF 0x3f3f3f3f
#define int long long

using namespace std;
typedef long long ll;

int n;
const int N = 1e6+10;
int a[N];
int dp[N];

signed main(){
    cin >> n;
    for(int i = 0 ; i < n ; i++){
        cin >> a[i];
    }
    dp[0] = a[0];
    int maxx = dp[0];
    for(int i = 1 ; i < n ; i++){
        //由于是要的连续片段，这一步相当于判断了是重新开始，还是继续保持连接
        dp[i] = max(a[i],dp[i-1]+a[i]);
        maxx = max(maxx,dp[i]);
    }
    cout << maxx;
}