[C++知识库]PAT (Advanced Level) 1007 Maximum Subsequence Sum (模拟 贪心 C++ 测试点4)

题意：

给出一个长度为$1e4$的序列，求最大连续子段和以及起始结束位置的数。
注意：如果所有的数都为负数，最大和为$0$,起始结束位置为$1,n$

思路：

• 贪心的考虑，如果$a_i<0$是没有意义的，所以只需要遍历一遍，每次碰到$a_i<0$的记录答案并且重新计算即可。

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=10000+10;
ll a[maxn],n;
int main(){
	ll tmp=0,ans=-1,resl,resr,las=1;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	} 
	for(int i=1;i<=n;i++){
		tmp+=a[i];
		if(tmp<0){
			tmp=0;
			las=i+1;
		}
		else if(tmp>ans){
			ans=tmp;
			resl=las;resr=i;
		}
	}
	if(ans<0) ans=0,resl=1,resr=n;
	cout<<ans<<" "<<a[resl]<<" "<<a[resr]<<endl;
	return 0;
}