HDU 1087 最大上升子序列和：動態規劃經典模板題

問題描述

給定 n 個正整數，找到一個嚴格遞增子序列，使其元素和最大。n ≤ 1000，數值為 32 位整數。多測試用例，以 0 結束。

動態規劃建模

定義 dp[i] 表示以第 i 個數結尾的最大上升子序列和。狀態轉移方程：

dp[i] = max(dp[j] + num[i])  (num[j] < num[i], j < i)
dp[i] = num[i]  (基礎情況：自身構成子序列)

算法流程

1. 初始化 dp[i] = num[i]
2. 雙重循環：外層 i 從 1 到 n，內層 j 從 1 到 i-1
3. 若 num[j] < num[i]，更新 dp[i] = max(dp[i], dp[j] + num[i])
4. 維護全局最大值 ans = max(ans, dp[i])

標準實現（C）

#include 
#define MAX 1010
int dp[MAX], num[MAX];

int main() {
    int n;
    while (~scanf("%d", &n) && n) {
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &num[i]);
            dp[i] = 0;
        }
        int ans = -1e9;
        for (int i = 1; i <= n; ++i) {
            dp[i] = num[i];
            for (int j = 1; j < i; ++j)
                if (num[j] < num[i])
                    dp[i] = max(dp[i], dp[j] + num[i]);
            ans = max(ans, dp[i]);
        }
        printf("%d\n", ans);
    }
    return 0;
}

複雜度分析

• 時間：O(n^2)，n=1000 時 10^6 操作，輕鬆通過
• 空間：O(n)

優化方向（拓展）

若 n 较大（如 10^5），可使用值域線段樹或 BIT 將內層查詢優化為 O(log V)，總複雜度 O(n log V)。但本題數據範圍 O(n^2) 完全足夠。

避坑指南

• 注意「嚴格遞增」條件：num[j] < num[i]，不是 ≤
• 初始化 ans 為負無窮，防止全負數序列（雖然題目說正整數）
• 多測試用例需正確重置數組
• 輸入結束標誌為單獨一行 0

DP 思想精髓

「將複雜問題分解為重疊子問題，通過狀態定義與轉移方程，自底向上構建最優解。」此題完美展示了 DP 化繁為簡的威力：原本指數級的子序列枚舉，通過「以 i 結尾」的狀態定義，化為多項式時間可解。