11.19 p1115最大字段和

点击查看代码

#include<bits/stdc++.h>using namespace std;int n;int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin>>n;int a,b;int ans=-1e4-1;for(int i=0;i<n;++i){cin>>a;if(i==0) b=a;else b=max(a,b+a);ans=max(b,ans);}cout<<ans<<endl;return 0;
}

本题应用了动态规划或者说状态机的思想，从前到后检测前段和和当前值的大小，更新前段和和答案，挺好的