九度 OJ 1011 最大連續子序列和 - DP 輸出首尾元素

問題描述

給定 K 個整數序列，求最大連續子序列和，並輸出該子序列的第一個和最後一個元素。若多解，取下標最小者；若全負，和為 0，輸出首尾元素。

DP 狀態定義

dp[i]：以 i 結尾的最大子序列和。start[i]：對應子序列的起始下標。

轉移：

• 若 dp[i-1] + a[i] >= a[i]，則 dp[i] = dp[i-1] + a[i], start[i] = start[i-1]。
• 否則 dp[i] = a[i], start[i] = i。

掃描過程中記錄全局最大值及其起終下標。全負情況特殊處理。

代碼實現（C++）

#include 
#include 
using namespace std;

int main() {
    int n;
    while (cin >> n && n) {
        int a[10000], dp[10000], start[10000];
        for (int i = 0; i < n; i++) cin >> a[i];
        bool allNeg = true;
        for (int i = 0; i < n; i++) if (a[i] >= 0) { allNeg = false; break; }
        if (allNeg) {
            cout << 0 << ' ' << a[0] << ' ' << a[n-1] << endl;
            continue;
        }
        dp[0] = a[0]; start[0] = 0;
        int maxSum = dp[0], bestL = 0, bestR = 0;
        for (int i = 1; i < n; i++) {
            if (dp[i-1] + a[i] >= a[i]) {
                dp[i] = dp[i-1] + a[i];
                start[i] = start[i-1];
            } else {
                dp[i] = a[i];
                start[i] = i;
            }
            if (dp[i] > maxSum) {
                maxSum = dp[i];
                bestL = start[i];
                bestR = i;
            }
        }
        cout << maxSum << ' ' << a[bestL] << ' ' << a[bestR] << endl;
    }
    return 0;
}

關鍵點

• 記錄起始下標 start[i] 以輸出首尾元素。
• 全負數判斷單獨處理，輸出 0 和首尾元素。
• 若最大值不唯一，題目要求下標最小，故更新條件用 > 而非 >=。