原题目
Given a sequence of K integers
. A coutinuous subsequence is defined to be
where 1 ≤ i ≤ j ≤ K. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.
Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.
Input Specification:
Each input file contains one test case. Each case occupies two lines. The first line contains a positive integer K (≤ 10000). The second line contains K numbers, separated by a space.
Output Specification:
For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence is not unique, output the one with the smallest indices i and j (as shown by the sample case). If all the K numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.
Sample Input:
10
-10 1 2 3 4 -5 -23 3 7 -21
Sample Output:
10 1 4
题目大意
给定一个整数序列，求该序列的连续子序列的最大和。
输入第一行包含一个正整数K，表示该序列的元素个数。输入第二行包含K个整数，为序列的元素。
输出一行三个整数，分别表示序列的连续子序列的最大和、和最大的子序列的首尾元素值。
注意：
- 当序列的和最大的连续子序列不唯一时，只需输出首元素的序号最小的子序列的首尾元素值。
- 当序列的K个元素均为负时，序列的子序列的和的最大值定为0，且需输出该序列的第一个和最后一个元素值。
题解
用动态规划的思想，维护一个数组，数组的第i个元素表示以i结尾的连续子序列的和的最大值。数组的状态转移方程为：
找到连续子序列最大和的结尾元素，然后往前找到该子序列的开头元素，然后输出即可。
C语言代码如下：
#include<stdio.h>
#include<stdlib.h>
#define max(a, b) (a) > (b) ? (a) : (b)
int main(){
int k, maxx = 0; //一开始想的是maxx初始化为0，若数组全负可以不用判断maxx的值直接输出，
//结果给自己挖了个坑，没注意到最大值恰好为0的情况。
scanf("%d\n", &k);
int start = 0, end = k - 1;
int *nums = malloc(sizeof(int) * k);
int *max_subsequence_sums = malloc(sizeof(int) * k);
for(int i = 0;i < k;++i){
scanf("%d", nums + i);
if(!i)
max_subsequence_sums[0] = nums[0];
else{
max_subsequence_sums[i] = max(max_subsequence_sums[i - 1] + nums[i], nums[i]);
}
if(max_subsequence_sums[i] > maxx){
end = i;
maxx = max_subsequence_sums[i];
}
}
if(!maxx){
for(int i = 0;i < k;++i)
if(!nums[i]){
printf("0 0 0\n");
return 0;
}
}
int tmp = maxx;
for(int i = end; tmp > 0;--i){
tmp -= nums[i];
start = i;
}
while(start >=1 && !nums[start - 1]) //这一段代码是考虑到最大连续子序列和非零
//但子序列可能以0开头的情况，但是貌似测试点里没有相应的数据
start--;
printf("%d %d %d\n", maxx, nums[start], nums[end]);
return 0;
}
第一遍写的时候没看清题目，以为是输出和最大的连续子序列的首尾序号，结果只能过一个点。看清题目后没写23 - 29行的代码，测试点5始终过不了。在网上找了一下发现原因在于当序列的最大和为0时程序输出结果本来应为0 0 0，但实际却把序列当成了全负，输出了序列的首尾元素，显然是不对的。所以又遍历了一遍数组判断是否为全负。
另外，题目中的状态转移数组完全可以用一个变量表示，额外内存空间可以由O(n)变为O(1)。
更改后的代码如下：
#include<stdio.h>
#include<stdlib.h>
#define max(a, b) (a) > (b) ? (a) : (b)
int main(){
int k, maxx = -1; //maxx置为-1，输入完后若maxx为负则整个数组全为负数。
scanf("%d\n", &k);
int start = 0, end = k - 1;
int *nums = malloc(sizeof(int) * k);
int max_subsequence_sum;
for(int i = 0;i < k;++i){
scanf("%d", nums + i);
if(!i)
max_subsequence_sum = nums[0];
else{
max_subsequence_sum = max(max_subsequence_sum + nums[i], nums[i]);
}
if(max_subsequence_sum > maxx){
end = i;
maxx = max_subsequence_sum;
}
}
if(maxx < 0){
printf("%d %d %d\n", 0, nums[0], nums[k - 1]);
return 0;
}
int tmp = maxx;
for(int i = end;i >= 0;--i){
if(tmp == nums[i]){
start = i;
break;
}
tmp -= nums[i];
}
printf("%d %d %d\n", maxx, nums[start], nums[end]);
return 0;
}
网上看到别人有直接用结构体来记录的，可以在一遍读入后直接输出结果。精力有限就不再改了。
