PAT甲级1007. Maximum Subsequence Sum

桃扇骨 2022-06-11 03:25 134阅读 0赞

Given a sequence of K integers \{ N1, N2, …, NK \}. A continuous subsequence is defined to be \{ Ni, Ni+1, …, Nj \} 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 1 2 3 4 -5 -23 3 7 -21

Sample Output:

10 1 4

### 题目要求： ###

给定一列数，然后求出这一列数中和最大的子列；第一行为输入的数列的数字个数，第二行为给定的数列；要求输出最大和子列的和、最大和子列的首元素、最大和子列末尾元素；数与数之间使用空格隔开，最后一个数后面没有空格；若给定的子列有多个最大和子列，那么按照第一个和子列输出；若给定的数列全部是负数，那么最大子列的和为0，最大子列的首元素为给定数列的首元素，最大子列的末尾元素为给定子列的末尾元素；

### 解题思路： ###

sum，为最大子列的的和，sumTemp为最大子列的临时值，leftTmp为sumTemp的下标；依次输入数字，sumTmp+=input,如果sumTmp<0,都应该将leftTmp右移，并令sumTmp=0,相当于将临时子数列舍弃，重新构建一个临时子数列;因为sumTmp<0时无论后面输入的数如何，前面的临时子数列和都会让整体的临时子数列的和减小；

#include "stdio.h"
    #include "stdlib.h"
    #include <stdbool.h>
    
    int main() {
    
        int count, sum = -1, sumTmp = 0, left = 0, leftTmp = 0, right = 0, input, first, last;
    
        int num[10000];
    
        bool positive = false, half_positive = false;
    
    
        scanf("%d", &count);
    
        for (int i = 0; i < count; i++)
        {
    
            scanf("%d", &input);
            num[i] = input;
            if (input >= 0)
            {
                positive = true;
            }
    
            sumTmp = sumTmp + input;
            if (sum < sumTmp)
            {
                left = leftTmp;
                right = i;
                sum = sumTmp;
            }
            else if (sumTmp < 0)
            {
                leftTmp=i+1;
                sumTmp = 0;
            }
    
        }
    
        if (positive)
        {
            printf("%d %d %d", sum, num[left], num[right]);
        }
        else
        {
            printf("%d %d %d", 0, num[0], num[count-1]);
        }
    
        system("pause");
        return 0;
    }

### 总结： ###

又一次看错了题目，以为输出的是最大子数列的和、最大子数列的下标和上标！！！！即使输出的是上标和下标也会通过测试用例，并且通过平台的部分测试；

本题中容易被忽略的数列类型有如下：

*  连续0
    
    5
    
    0 0 -1 -1 0
 *  前面都为负、最后一位为0
    
    5
    
    \-1 -1 -1 -1 0