题解 | 最大连续子序列

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{

	int n;
	while(cin>>n)
	{
		if(n==0) break;
	
		//cin>>n;
		int arr[10000];
		int front[10000];
		int end;
		int dp[10000];
		//int maxnum=-1000;
		for(int i=0;i<n;i++)
		{
			cin>>arr[i];
		}
		
		dp[0]=arr[0];
		front[0]=0;
		int mi=0;
		int maxnum=dp[0];
		
		int count=0;
		for(int h=0;h<n;h++)
		{
			if(arr[h]<0)
			{
				count++;
			}
		}
		
		if(count==n)
		{
			cout<<0<<" "<<arr[0]<<" "<<arr[n-1]<<endl;
		}
		else
		{
			for(int i=1;i<n;i++)
		  {
			dp[i]=max(arr[i],dp[i-1]+arr[i]);
			if(maxnum<dp[i])
			{
				mi=i;
			}
			maxnum=max(maxnum,dp[i]);
			
			if(arr[i]>dp[i-1]+arr[i])
			{
				front[i]=i;
				end=i;
			}
			else{
				front[i]=front[i-1];
				end=i;
			}
	      }
		  cout<<maxnum<<" "<<arr[front[mi]]<<" "<<arr[mi]<<endl;
		}
    }
	return 0;
}