1007 Maximum Subsequence Sum (25分)

1007.png

分析：

本題要求最大連續(xù)子序列的和，輸出最大之和以及子序列第一個(gè)數(shù)和最后一個(gè)數(shù)。如果方案不唯一，則輸出i，j最小的一組。如果所有數(shù)都是負(fù)數(shù)，則最大和為0，然后輸出首尾元素。
先考慮如何求最大和。以dp[i]表示以A[i]作為末尾的連續(xù)序列最大和。以本題為樣例dp[0]=-10,dp[1]=1,dp[2]=3......容易知狀態(tài)轉(zhuǎn)移方程為dp[i]=max{A[i],dp[i-1]+A[i]}。通過遍歷就可通過dp[0]把所有dp求出來，最大和就是dp數(shù)組中最大的數(shù)。
再考慮如何求最大連續(xù)子序列的首位元素，以s[i]表示以A[i]作為結(jié)尾的最大連續(xù)子序列是從哪個(gè)元素開始，根據(jù)狀態(tài)轉(zhuǎn)移方程易知s[i]=i或者s[i]=s[i-1]。
在一開始的時(shí)候先考慮所有數(shù)是負(fù)數(shù)的情況，節(jié)省時(shí)間。

C++:

#include <cstdio>

const int maxn = 10010;

int arr[maxn], dp[maxn], s[maxn];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    //先處理全為負(fù)數(shù)的情況
    bool flag = false; //是否有正數(shù)
    for (int i = 0; i < n; i++) {
        if (arr[i] >= 0) {
            flag = true;
            break;
        }
    }
    if (flag == false) {
        printf("0 %d %d\n", arr[0], arr[n - 1]);
        return 0;
    }
    dp[0] = arr[0];
    s[0] = 0;
    for (int i = 1; i < n; i++) {
        if (dp[i - 1] + arr[i] > arr[i]) {
            dp[i] = dp[i - 1] + arr[i];
            s[i] = s[i - 1];
        } else {
            dp[i] = arr[i];
            s[i] = i;
        }
    }
    int index = 0;//dp數(shù)組最大值的下標(biāo)
    for (int i = 1; i < n; i++) {
        if (dp[i] > dp[index]) {
            index = i;
        }
    }
    printf("%d %d %d\n", dp[index], arr[s[index]], arr[index]);
    return 0;
}