PAT 1007 Maximum Subsequence Sum (25分) 最大连续子序列和

题目

Given a sequence of K integers { N​1​​ , N​2​​ , ..., N​K​​ }. A continuous subsequence is defined to be { Ni​​ , 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

题目大意

给定一个整数序列，让找出其中 和 最大的 连续子序列，输出这个序列的和、起始元素、结尾元素。如果有多个和最大的连续子序列，输出其中开始元素和结束元素下标最小（也就是最靠前）的那个子序列。如果所有整数都是负数，规定和为0，输出序列的首元素和尾元素。

思路分析

• maxSum表示最大的子序列和，初始化为-1，在最后判断一下如果它为-1，说明全为负数，把它赋值为0。
• leftIndex表示最终子序列的第一个元素在序原列中的下标，初始化为0，rightIndex表示最终子序列的最后一个元素在序原列中的下标，初始化为序列长度-1。
• 我们维护一个临时的连续子序列寻找局部最优解，从数组第一个元素开始，累加当前元素，每当它的和 > maxSum时，就用它取代全局最优（它的起点作为最终起点，它的终点（当前元素的位置）作为最终终点）；每当它的和 < 0 时，就舍弃之前的元素，从下一个位置重新开始累加统计。为什么舍弃？因为它现在是负数，不管下一个元素是正是负，加起来只会变得更小，所以舍弃它重新开始。
• 这样做法有个好处是，如果全是负数，临时序列的和永远不会大于maxSum（初始值是-1），所以就不会改变 leftIndex（0） 和 rightIndex（序列长度-1），是满足题意得，这样我们最终输出就不用特殊处理。
• 不太明白得话，看看代码，注释很详细，容易看懂。

代码

#include <iostream>
#include <algorithm>
using namespace std;

int main() {

    // k个整数
    int k;
    cin >> k;
    int num[k];
    for (int i = 0; i < k; ++i)
        cin >> num[i];
    // 递增序列起始位置，结束位置
    int leftIndex = 0, rightIndex = k - 1;
    // 临时的连续和，临时连续和的起始位置，最大连续和
    int tempSum = 0, tempIndex = 0, maxSum = -1;
    for (int i = 0; i < k; ++i) { 
        // 累加临时的连续和
        tempSum += num[i];
        // 若小于0，则从下一个位置开始重新统计
        if (tempSum < 0) {
            tempSum = 0;
            tempIndex = i + 1;
        // 一旦这一个临时连续序列的和超过了之前的最大和
        // 如果元素全为负数，这个条件不会成立，leftIndex=0,rightIndex=k-1不会被改变
        } else if (tempSum > maxSum){
            // 更新最大和
            maxSum = tempSum;
            // 临时序列的起始位置成了最终序列的起始位置
            leftIndex = tempIndex;
            // 当前位置（临时序列的结束位置）成为最终序列结束位置
            rightIndex = i;
        }
    }
    // 全为负数的情况下，返回累加和0
    if (maxSum < 0) maxSum = 0;
    // 输出最大和，连续序列的第一个数字（是值，不是位置），最后一个数字
    cout << maxSum << " " << num[leftIndex] << " " << num[rightIndex];

    return 0;
}