Maximum Subsequence Sum
【题目地址】PTA
【题目】
01-复杂度2 Maximum Subsequence Sum (25分)
Given a sequence of K integers { N?1??, N?2??, …, N?K?? }. A continuous subsequence is defined to be { N?i??, N?i+1??, …, N?j?? } 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
【题目分析】
基本思路：在线处理，不断更新下标
要注意的问题：
1.要输出的是元素的值，而不是元素下标。
2.maxsum<0
=> 全负数，输出 0 array[0] array[N-1] (题干规定)
3.maxsum=0
=> 由0和负数共同构成 ，输出 0 0 0（当0为最大子列和的时候，最大子列为连续个0，又因为输出的是值不是下标…）
4.
int thisleft=0; int maxleft=0; int maxright=0;
定义当前子列左下标，最大子列左右下标
5.
maxleft=thisleft; maxright=i;
若子列在增长，更新左右下标；
thisleft=i+1;
若前子列被舍弃，更新当前左下标；
6.如果有相同的最大子列怎么办？
if(thissum>maxsum)
不包括等于，只记录处理最先出现子列。
7.为什么maxsum要初始化为无穷小==-INF==？
如果初始化为0，全负数的例子会挂掉.
因为thissum（负数）< maxsum（0），maxsum永远不会更新为负数，这样后面的判断条件 maxsum<0 => 全负数 没办法成立。所以直接取负无穷小，使其能不断更新负数值
【代码】
#include<stdio.h>
#include<stdlib.h>
#define INF 0x3f3f3f3f
int * array;
int N;
void getelement()
{
scanf("%d",&N);array=(int *)calloc(N,sizeof(int));for(int i=0;i<N;i++){
scanf("%d",array+i);}return 0;
}
void sum3()
{
int thissum=0;int maxsum=-INF ;int thisleft=0;int maxleft=0;int maxright=0;for(int i=0;i<N;i++){
thissum+=*(array+i);if(thissum>maxsum){
//大于而不是大于等于，只处理第一个最大子列和maxsum=thissum;maxleft=thisleft;maxright=i; };if(thissum<0){
thissum=0;thisleft=i+1;};}if(maxsum<0) printf("%d %d %d",0,*array,*(array+N-1));if(maxsum==0)printf("%d %d %d",0,0,0);if(maxsum>0)printf("%d %d %d",maxsum,*(array+maxleft),*(array+maxright));return 0;
}
int main(void)
{
getelement();sum3();return 0;}