7-7 最大连续子序列 (10 分)

7-7 最大连续子序列 (10 分)

给定K个整数的序列{ n 1 ，n 2 ，…，n K }，其任意连续子序列可表示为{ n i ，n i+1 ，…，n j​ }，其中 1≤i≤j≤K。最大连续子序列是所有连续子序列中元素和最大的一个。例如，给定序列{ -2，11，-4，13，-5，-2 }，其最大连续子序列为{ 11，-4，13 }，最大和为20。 要求编写程序得到最大和，并输出子序列的第一个元素和最后一个元素。

输入格式:
测试数据有多组。每组测试数据输入两行，第一行给出一个正整数K（0

输出格式:
对于每组测试，在一行里输出最大和、最大连续子序列的第一个和最后一个元素，数据之间用空格分隔。如果最大连续子序列不唯一，则输出序号i和j最小的那个。若所有K个元素都是负数，则定义其最大和为0，再输出整个序列的第一个和最后一个元素。

输入样例:

6
-2 11 -4 13 -5 -2
0

输出样例:

20 11 13

知识点：动态规划，

思路：本题要求最大连续子序列和，可以用动态规划进行求解用数组dp来存储子序列的和，dp[i]=max(dp[i-1]+a[i],a[i]);即当前一项dp[i-1]大于零dp[i]=dp[i-1]+a[i],当前一项dp[i-1]小于零舍弃，从a[i]重新开始选取子序列和

注意事项：题中说了有多组数据所以while(cin>>k)，并且ans，v在进行寻找maxsub时要进行初始化。

源码：

#include
using namespace std;
int a[1005];
int k;
int dp[1005];
int ans = -1;
int u, v=1;
void maxsub() {
    ans=-1;
    v=1;
	for (int i = 1;i <= k;i++) {
		dp[i] = max(dp[i-1] + a[i], a[i]);
		if (ans < dp[i]) {
			ans = dp[i];
			u = i;
		}
	}
	for (int i = u;i >= 1;i--) {
		if (dp[i] < 0) {
			v = i+1;
			break;
		}
	}
}
int main() {
	while (cin >> k) {
		if (k == 0)
			return 0;
		for (int i = 1;i <= k;i++) {
			cin >> a[i];
		}
		maxsub();
		if (ans == -1) {
			cout << "0" <<" "<< a[1] <<" "<< a[k] << endl;
		}
        else
		    cout << ans << " " << a[v] << " " << a[u] << endl;
	}
	return 0;
	
}