01-复杂度2 Maximum Subsequence Sum (25分)

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<cctype>
#include<cmath>
#include<vector>
#include<set>
#include<map>
#include<sstream>
#define mm(a,x) memset(a,x,sizeof(a))

using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int maxn=10005;


int main() {
   
	int first,last,temp;
	int thismax,thissum;
	int a[maxn];
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	cin>>a[i];
	thissum=0;
	thismax=-1;
	for(int i=0;i<n;i++)
	{
   
		thissum+=a[i];
		if(thissum>thismax)
		{
   
			thismax=thissum;
			first=temp;
			last=i;
		}
		else if(thissum<0)
		{
   
			thissum=0;
			temp=i+1;
		}
	}
	if(thismax>=0)
	cout<<thismax<<" "<<a[first]<<" "<<a[last]<<endl;
	else{
   
		cout<<0<<" "<<a[0]<<" "<<a[n-1];
	}
}