pat 甲級 A1007 Maximum Subsequence Sum (25分)

題目連結：

https://pintia.cn/problem-sets/994805342720868352/problems/994805514284679168

題目分析：

最大子序列和的問題。注意，若序列中全為負數，則輸出第一個元素以及最後一個元素。且和為零。

參考代碼：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=10010;
int a[N], dp[N];    //dp[i]表示以i結尾的最大序列和
int s[N] = {0};      //s[i]表示以i結尾的最大序列和的起始節點位置
int main(){
    int k, j = 0;
    scanf("%d",&k);
    bool flag = false;
    for(int i = 0; i < k; i++){
        scanf("%d",&a[i]);
        if(a[i] >= 0) flag = true;
    }
    if(flag == false){
        printf("0 %d %d\n",a[0], a[k-1]);
        return 0;
    }
    dp[0] = a[0];
    for(int i = 1; i < k; i++){
        dp[i] = max(dp[i-1] + a[i], a[i]);
        if(dp[i] > a[i]) s[i] = s[i-1];
        else s[i] = i;
    }
    for(int i = 1; i < k; i++){
        if(dp[i] > dp[j])  j=i;
    }
    printf("%d %d %d",dp[j], a[s[j]], a[j]);
    return 0;
}