526互联

PAT-甲级-1007 Maximum Subsequence Sum C++

发布时间 2023-07-13 12:38:57作者: 正明小佐

Given a sequence of  integers { , , ..., ​ }. A continuous subsequence is defined to be { , , ...,  } where . 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  (). The second line contains  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  and  (as shown by the sample case). If all the  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

题意：

求一个数列的最长连续子序列和，输出序列和大小，和起始位置

分析：

很容易想到，需要用一个tempSum来记录临时的子序列和，用lastSum来记录之前的子序列和，遍历数组，当tempSum<0时，需要抛弃之前的子序列，令tempSum重新为0，tempIndex = i + 1；当tempSum≥0时，则可以分为两种情况，第一种是当前子序列和tempSum大于之前的子序列和lastSum，此时需要更新left和right的指向位置，并更新lastSum。因为这时有更大的子序列和出现了，所以right指向当前数组的指向i，而left更新为第一个使子序列和≥0的位置，即tempIndex。若tempSum ≤ lastSum，但是这时tempSum依然≥0，后面可能出现一个更大的正数，来使tempSum ＞ lastSum，所以继续遍历，如果之后没有出现tempSum > lastSum的情况，比如 [1, 2, 3, 4, -5, -2]，这时因为最后一次更新left和right是在i指向4的位置，后面均不用更新，因此这种情况不需要处理，只用继续遍历即可。综上，最长连续子序列和一次遍历可以解决问题。

代码：

//
// Created by yaodong on 2023/7/12.
//
#include "iostream"


int main() {
    int n;
    std::cin >> n;
    int seq[n];
    int temp;
    for (int i = 0; i < n; ++i) {
        std::cin >> temp;
        seq[i] = temp;
    }

    int left = 0, tempSum = 0, right = n - 1, lastSum = -1;
    int tempIndex = 0;
    for (int i = 0; i < n; ++i) {
        tempSum += seq[i];
        if(tempSum < 0){
            tempSum = 0;
            tempIndex = i + 1;
        }else if(tempSum > lastSum){
            lastSum = tempSum;
            left = tempIndex;
            right = i;
        }
    }
    if(lastSum < 0) lastSum = 0;
    printf("%d %d %d", lastSum, seq[left], seq[right]);
}