PAT(Advanced)1007 Maximum Subsequence Sum (25 分)

1007 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\le i\le j\le 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$ ($\le 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：

题目解读：给定一个数列，求它的最大子串合及子串的起点和终点。

解题思路：最大子串合即Send – Sstart-1，中间串即是Astart,Astart+1, … , Aend，注意每一次更新max的大小，以及把0归入，这道题有几个测试点比较麻烦，如果只有负数和0的时候，应该输出的是“0 0 0”，除此之外的全负数都应该输出“0 起点 终点”。此外，这道题的很多数值都要初始化的，因为没有初始化有过运行时错误和段错误。除此之外还有一个测试点没，还需要找bugqaq！！

非AC代码

#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
    int sum[10010],num[10010];
    fill(sum,sum+10010,0);
    fill(num,num+10010,0);
    int n,flag1=0,flag2=0;
    cin >> n;
    for( int i = 1 ; i <= n ; i ++ ){
        cin >> num[i];
        if(num[i] >= 0){
            flag1 = 1;
            if(num[i] > 0){
                flag2 = 1;
            }
        }
        sum[i] = sum[i-1]+num[i];
    }
    int start=1,end=1,max=0;
    int j;
    for( int i = 1 ; i <= n ; i ++){
        if(sum[i] >= sum[i-1]){
            for( j = i ; j <= n ; j ++ ){
                if( sum[j] >= sum[j+1])
                    break;
            }
                if(sum[j]-sum[i-1] > max){
                    start = i;
                    end = j;
                    max = sum[j]-sum[i-1];
                }
        }
    }
    if(!flag1){
        cout << "0 " << num[1] << " " << num[n] << endl;
    }
    else if( flag1 && !flag2 ){
        cout << "0 0 0" << endl;
    }
    else{
        cout << max << " " <<  num[start] << " " << num[end] << endl;
    }

    return 0;
}

Version 2:

修改了一个错误（但是好像不是它的测试点）

输入测试数据 5 9 -9 -9 -9 9 得到错误答案 18 9 0

检查后发现是i、j循环里面，j遍历会到n+1之后退出，即最后一个元素的后面一个位置，为了防止这个溢出，检测一下j是否为n+1，若为n+1则设回n。

#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
    int sum[10010],num[10010];
    fill(sum,sum+10010,0);
    fill(num,num+10010,0);
    int n,flag1=0,flag2=0;
    cin >> n;
    for( int i = 1 ; i <= n ; i ++ ){
        cin >> num[i];
        if(num[i] >= 0){
            flag1 = 1;
            if(num[i] > 0){
                flag2 = 1;
            }
        }
        sum[i] = sum[i-1]+num[i];
    }
    int start=1,end=1,max=0;
    int j;
    for( int i = 1 ; i <= n ; i ++){
        if(sum[i] >= sum[i-1]){
            for( j = i ; j <= n ; j ++ ){
                if( sum[j] >= sum[j+1] )
                    break;
            }
            if(j == n+1 ) j = n;
                if(sum[j]-sum[i-1] > max){
                    start = i;
                    end = j;
                    max = sum[j]-sum[i-1];
                }
        }
    }
    if(!flag1){
        cout << "0 " << num[1] << " " << num[n] << endl;
    }
    else if( flag1 && !flag2 ){
        cout << "0 0 0" << endl;
    }
    else{
        cout << max << " " <<  num[start] << " " << num[end] << endl;
    }

    return 0;
}