一开始以为用前缀和做，看了下数据10000，果断放弃。
思考了一下，最大和序列的第一个数必为正数（废话），关键是从头开始的子序列和也必为正数。如果加到某个地方和为负数，我还要你前面这些数何用，不如从后面开始重新选。基于上述思路就可以写出代码了。
#include <iostream> #include <cstring> #include <string> #include <sstream> #include <string> #include <cstdio> #include <algorithm> #include <vector> #define maxn 10005 #define INF 0x3f3f3f3f #define EPS 1e-6 #define pi acos(-1.0) using namespace std; typedef long long ll; int n; int a[maxn]; int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; int flag; for(flag=1;flag<=n;flag++) { if(a[flag]>=0) break; } if(flag==n+1) { cout<<0<<" "<<a[1]<<" "<<a[n]<<endl; return 0; } int maxx=-1; int sum=0; int s,t,tmp=1; for(int i=1;i<=n;i++) { sum+=a[i]; if(sum>maxx) { maxx=sum; s=tmp; t=i; } else if(sum<0) { sum=0; tmp=i+1; } } cout<<maxx<<" "<<a[s]<<" "<<a[t]<<endl; return 0; }
原文：https://www.cnblogs.com/FTA-Macro/p/10046989.html
