1007 Maximum Subsequence Sum 求解最大字段和问题 详解

目录

题目

输入样例1（题目自带）

输出样例1

输入样例2（自编，特殊情况）

输出样例2

提交结果截图

解题思路及源代码

题目

 题目链接：1007 Maximum Subsequence Sum （PAT (Advanced Level) Practice）

输入样例1（题目自带）

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

输出样例1

10 1 4

输入样例2（自编，特殊情况）

3 
-1 -2 -3

输出样例2

0 -1 -3

提交结果截图

解题思路及源代码

/******************************************************
 * 解题思路：
 * 1.用一个数组来存储长度为N的序列sequence[10001]
 * 2.用一个sum变量记录所求子序列的和
 * startloc为所求子序列起始位置，
 * endloc为所求子序列结束位置。
 * cur_sum变量记录当前子序列的和
 * cur_startloc为当前子序列起始位置，
 * cur_endloc为当前子序列结束位置。
 * 3.分析样例：
 * 序列   0 1 2 3 4  5  6  7 8  9
 *      -10 1 2 3 4 -5 -23 3 7 -21
 * a.从一个负数开始加，不管后面加什么都不可能是所求的
 * 和最大的子序列.
 * b.如果加了一个数后，比原来发现的最大子序列和大，则
 * 更新最大子序列和，并记录位置。
 * c.如果加了一个数后，没有比原来发现的最大子序列和大，
 * 但也没有变成负数，则说明还有变得更大的机会，可以
 * 继续加下去。
 * d.而如果加了一个数后，变成了负数，则当前的序列就
 * 没有加下去的必要了，因为由a.可知应该放弃当前的子序列，
 * 从下一个位置重新开始加。
 * 4.根据上述的分析就很容易写出代码了。
******************************************************/

#include <iostream>
using namespace std;

int main()
{
    int N;
    cin>>N;
    int* sequence = new int [N];
	int sum = -1, startloc = 0, endloc = 0;
	int cur_sum = 0,cur_startloc = 0, cur_endloc = 0;
 	for(int i = 0; i < N; i++)
		cin>>sequence[i];
	for(int i = 0; i < N; i++)
	{
		cur_sum += sequence[i];
		if(cur_sum > sum)
		{
			sum = cur_sum;
			cur_endloc = i;
			startloc = cur_startloc;
			endloc = cur_endloc;
		}
		else if(cur_sum < 0)
		{
			cur_sum = 0;
			cur_startloc = cur_endloc = i+1;
		}
	}
	if(sum < 0)
	{
		sum = 0;
		startloc = 0;
		endloc = N-1;
	}
	cout<<sum<<" "<<sequence[startloc]<<" "<<sequence[endloc];
	delete[]sequence;
	return 0;
}