PAT甲级 1007 Maximum Subsequence Sum (25分)

1007 Maximum Subsequence Sum (25分)

题目链接：PAT A 1007

引子：这道题其实就是对求最大连续子序列和的题的改进，求最大连续子序列和常用的有三种方法，其中最快的就是在线处理方法，可以达到O（N）的时间复杂度。具体思想就是定义thissum = 0, maxsum = 0，分别表示当前累加元素和与最大和，然后thissum逐个加数组元素，如果大于maxsum，就更新maxsum的值。如果thissum<0，那么让thissum = 0，这是因为如果当前累加和小于0，那么再加后面的元素一定会使后面元素和减小，不可能获得更大的子列和，所以直接赋值为0。如此继续下去，就可以获得最大子列和，思路很简单，大家可以对照代码理解一下~

最大子列和-在线处理方法：

#include<iostream>
#include<vector>
using namespace std;
int main() {
	int k;
	scanf("%d", &k);
	vector<int> v(k);
	for(int i = 0; i < k; i++)
		scanf("%d", &v[i]);
	int thissum = 0, maxsum = 0;
	for(int i = 0; i < k; i++) {
		thissum += v[i]; //累加 
		if(thissum > maxsum)
			maxsum = thissum; //更新 
		else if(thissum < 0)
			thissum = 0; //舍弃之前的和 
	}
	printf("%d", maxsum);
	return 0;
}
           

有了前面的基础，这道题就简单很多了。

思路分析：这道题就是找到最大的连续子序列和，并且输出该子序列第一个元素和最后一个元素的值，如果有多个这样的子列，就输出下标最小的。注意如果全是负数，那么就要输出0，以及整个输入数字的第一个元素和最后一个元素。首先定义left = 0, right = k - 1，middle = 0, middle起到的是一个中转的作用。之后定义thissum = 0，maxsum = -1，作用与在线处理方法中的一样（但是这里maxsum赋值为-1，作用马上说）。然后累加元素，如果thissum>maxsum，那么更新maxsum，同时left = middle（middle中转作用），right = i（right正好就是此时保持最大的最后一个元素下标）。如果thissum<0，就让thissum = 0，同时由于这个i已经使thissum小于0了，那么middle = i + 1，表示新子列的开始，注意不能让left = i+ 1，因为并不知道之后的thissum会不会大于maxsum，不要急于更新left值，这也是设置middle变量的意义所在。最后如果maxsum仍然等于-1，就说明肯定全部是负数，令maxsum = 0，之后直接输出就行了，这也是为什么一开始就使left = 0, right = k - 1。

AC代码：

#include<iostream>
#include<vector>
using namespace std;
int main() {
	int k;
	cin >> k;
	vector<int> v(k);
	for(int i = 0; i < k; i++)
		cin >> v[i];
	int left = 0, middle = 0, right = k - 1, maxsum = -1, thissum = 0;
	for(int i = 0; i < k; i++) {
		thissum += v[i]; //累加 
		if(thissum > maxsum) {
			maxsum = thissum;
			left = middle; //更新左索引 
			right = i; //更新右索引 
		}
		else if(thissum < 0) {
			thissum = 0;
			middle = i + 1; //更新中转值 
		}
	}
	if(maxsum == -1) //全为负数 
		maxsum = 0;
	cout << maxsum << " " << v[left] << " " << v[right];
	return 0;
}