此处列出核心代码 自己按需打包或添加循环

for(int i=0;i<n;i++){
        cin >> a;
        nans=max((a),nans+(a));
        ans=max(nans,ans);
}

注意到 $n\le 2\times10^5$，用前缀和暴力枚举是不成了，我们可以用dp来做。

设 $f[i]$ 为 $a[1]\sim a[i]$ 的最大子段和，初始 $f[1]=a[1]$。对于一个 $i$，无非就是两种情况：

$$f[i]=\begin{cases} a[i],\,f[i-1]\le0\\ f[i-1]+a[i],\,f[i-1]>0 \end{cases}$$

当 $f[i-1]\le0$ 时，无论如何 $f[i-1]$ 都不可能比 $a[i]$ 大，所以我们就开始一段新的区间；否则当 $f[i-1]>0$ 时，我们令其加上 $a[i]$ 以开始新的转移。

与LIS一样，答案并不一定就是 $f[n]$，而是 $\max_{1\le i\le n}f[i]$。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,INF=0x3f3f3f3f;
int n,f[N],ans=-INF;
int main(){
	scanf("%d",&n);
	for(int i=1,x;i<=n;i++){
		scanf("%d",&x);
		if(i==1||f[i-1]<=0)
			f[i]=x;
		else
			f[i]=f[i-1]+x;
		ans=max(ans,f[i]);
	}
	printf("%d",ans);
	return 0;
}