题目给出K个整数。一个连续的片段是指 N[i], N[i+1], …, N[j](1≤i≤j≤K),最大片段是指拥有最大片段和的片段。比如给出数据{ -2, 11, -4, 13, -5, -2 },它的最大片段是{ 11, -4, 13 }(最大片段和是20)。给出数据,要求你找出最大片段和,以及最大片段的首元素和尾元素。

输入格式 每个样例占两行,第一行包括一个正整数K(≤10000),第二行包括K个数字,用空格分隔。

输出格式 每个样例,一行内输出最大和,首元素,尾元素。数字用空格分隔,并且结尾没有多余空格。特别注意,最大的子序列并不是独一无二的,要求输出最小索引i和j。如果所有的数字是负数,那么它的最大和定义为0,你应该输出数字序列的第一个数和最后一个数。

输入样例

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

输出样例

10 1 4

Link Here.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
int main() {
	int k;
	bool existPositive = false;
	cin >> k;
	int *s = new int[k];
	for (int i = 0; i < k; i++) {
		cin >> s[i];
		if (s[i] >= 0) {
			existPositive = true;
		}
	}
 
	int currentSum = 0, finalSum = -1;//finalSum初始化为0,一个测试点不能通过
	int index = 0, beginIndex = 0, endIndex = k-1;
	for (int i = 0; i < k; i++) {
		currentSum += s[i];
		if (currentSum > finalSum) {
			finalSum = currentSum;
			beginIndex = index;
			endIndex = i;
		}
		else if (currentSum < 0) {
			index = i + 1;
			currentSum = 0;
		}
	}
	if (!existPositive) {
		cout << 0 << " " << s[0] << " " << s[k - 1];
	}
	else {
		cout << finalSum << " " << s[beginIndex] << " " << s[endIndex];
	}
	//system("pause");
	return 0;
}

之前在acmerblog看过类似的问题: 一维数组的连续子数组的最大和

思路是用一个临时和和最终和,当临时和小于零就从下一个数重新开始求和,并不断更新最终和,中途再记录一下子片段的始末元素。