PAT1007 Maximum Subsequence Sum

求最大连续子串和

 

 

Sample Input:

10
-10 1 2 3 4 -5 -23 3 7 -21

Sample Output:

10 1 4

 

 

 

 

#include <iostream>
#include <vector>
#include <string>
using namespace std;

void MaSubSum(const vector<int>& a) 
{ 
	int first = 0;
	int last = 0;
	long maxSum = a[0]; 
	for (int i = 0; i < a.size(); i++) 
	{ 
		long thisSum = 0; 
		for (int j = i; j < a.size(); j++) 
		{ 
			thisSum += a[j]; 
			if (thisSum > maxSum) 
			{
				first = i;
				last = j;
				maxSum = thisSum; 
			}
		} 
	} 
	if (maxSum < 0)
	{
		cout<<"0"<<" "<<a[0]<<" "<<a[a.size() - 1];
	}
	else
	{
		cout<<maxSum<<" "<<a[first]<<" "<<a[last];
	}

	return; 
}

int main()
{
	int K;
	cin>>K;
	vector<int> V;
	while(K--)
	{
		int i;
		cin>>i;
		V.push_back(i);
	}
	MaSubSum(V);
	return 0;
}