简单的dp

首先设状态：设 $f(i)$ 为 $i$ 结尾的最大子段和。转移要么就是在 $f(i-1)$ 后面继续加 $a_i$，要么就是 $a_i$ 本身。所以取最大值即可。方程：$f(i)=max(f(i-1),0)+a_i$（先前讨论的变形）。

然后把状态数组滚动掉（雾）。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int a[200005];

int main(){
	int n;scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",a+i);
	int ans=-2000000000,t=0;;
	for(int i=1;i<=n;i++){
		t+=a[i];
		ans=max(ans,t);
		t=max(t,0);
	}
	printf("%d",ans);
	
    return 0;
}