首先设状态：设 f(i)f(i)f(i) 为 iii 结尾的最大子段和。转移要么就是在 f(i−1)f(i-1)f(i−1) 后面继续加 aia_iai ，要么就是 aia_iai 本身。所以取最大值即可。方程：f(i)=max(f(i−1),0)+aif(i)=max(f(i-1),0)+a_if(i)=max(f(i−1),0)+ai （先前讨论的变形）。 然后把状态数组滚动掉（雾）。

X03蒟蒻一只，老师课上布置的动规学习任务罢了

#include<iostream> using namespace std; int main() { int n,ans=-1e9,sum=0,fumax=-0; cin>>n; for(int i=0;i<n;i++) { int temp; cin>>temp; sum+=temp; int fusum=-sum; if(sum+fumax>ans)ans=sum+fumax; if(fusum>fumax)fumax=fusum; }