题解 | 最大子数组和

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define quick ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int inf=0x3f3f3f3f,maxn=2e5+5,mod=998252334;
inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
	return s*w;
}
void solve(){
    int n=read();vector<int>arr(n+1);
    vector<int>dp(n+1);
    for(int i=1;i<=n;i++){
        arr[i]=read();
    }
    
    // for(int i=1;i<=n;i++){
    //     for(int j=i-1;j>=1;j--){
    //         dp[i]=max(dp[i],dp[i]+arr[j]);
    //     }
    // }
    for(int i=1;i<=n;i++){
        dp[i]=max(dp[i-1]+arr[i],arr[i]);
    }
    //for(int i=1;i<=n;i++) cout<<dp[i]<<' ';
    sort(dp.begin()+1,dp.end());
    cout<<dp[n]<<endl;
}
signed main(){
	int t=1;
//	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}