P1115 最大子段和（DP）

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
vector<int> vx;
inline int mp(int x) {return upper_bound(vx.begin(),vx.end(),x)-vx.begin();}
inline int log_2(int x) {return 31-__builtin_clz(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int lowbit(int x) {return x&-x;}
void solve()
{
	int n;
	cin>>n;
	int maxn = -2e9;
	//f[i]表示以i为结尾的最大子段和
	vector<int> a(n+1),f(n+1);
	for(int i=1;i<=n;++i) cin>>a[i];
	for(int i=1;i<=n;++i) f[i] = max(a[i],f[i-1]+a[i]), maxn = max(f[i],maxn);
	cout<<maxn<<'\n';
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T = 1;
	//cin>>T;
	while(T--)
	{
		solve();
	}
}