【PAT甲級】1007 Maximum Subsequence Sum

題目連結：1007 Maximum Subsequence Sum

思路

1. 采用掃描一遍，時間複雜度為O(n)的算法。
2. 本題要求找到段内總和最大的連續段，思路是從最小片段開始着手，假設兩段連續正數段，中間為負數，若前段與負數和仍為正數，那兩段加上正數的值必然大于後段的段内總和，形如3，-2，5，三段和6大于後段和5，将5看作一個新的小段即可，逐漸累加合成大段。
3. 于是在掃描過程中，首先選擇一個非負數作為起點，逐位向後掃描，直至和為負，則重新向後選擇新起點。
4. 過程中發現目前和大于最大和，更新最大起點與終點，注意若相等不更新，因為題目表明相等情況取小值，此條件同樣要求選擇起始點時包括了0。
5. 輸出時注意若一個點都沒有被納入，說明全段為負，按照題目要求輸出0，全段起點，終點。

#include <iostream>
using namespace std;

int main(){
    int K, sum = -1, start, end, a, flag = 0;
    int sum2 = -1, start2, end2;
    cin >> K;
    for(int i = 0; i < K; i++){
        cin >> a;
        if(!i) start = a;
        //選擇頭結點
        if(!flag){
            if(a>=0){
                start = a;
                end = a;
                sum = a;
                flag = 1;
            }
        }
        //選擇尾結點
        else{
            if(sum + a >= 0){
                end = a;
                sum += a;
            }
            else flag = 0;//加入尾結點後變成負數則重新選擇頭節點
        }
        //更新最大值
        if(sum > sum2){
            sum2 = sum;
            start2 = start;
            end2 = end;
        }
    }
    if(sum2 == -1) printf("0 %d %d", start, a);
    else printf("%d %d %d", sum2, start2, end2);
}