HDOJ 1024 Max Sum Plus Plus：一維動態規劃優化求解最大M子段和

問題描述

給定長度為N的整數序列，要求找出M個不相交的連續子段，使其總和最大。這是經典的「最大M子段和」問題，數據規模大（N up to 1,000,000），傳統二維DP會超時超內存，必須優化空間複雜度。

核心算法：滾動數組優化DP

狀態定義

• dp[j]：以第j個元素結尾的i個子段的最大和
• temp[j]：前j個元素中i個子段的最大和（不要求以j結尾）

狀態轉移方程

dp[j] = max(dp[j-1] + s[j], temp[j-1] + s[j])
temp[j-1] = max(temp[j-1], dp[j])  // 維護前綴最大值

關鍵洞察：第i輪迭代只依賴第i-1輪的temp數組，且dp[j]只依賴dp[j-1]和temp[j-1]，因此可以用兩個一維數組滾動覆蓋，空間複雜度從O(MN)降至O(N)。

完整實現代碼

#include 
#include 
#include 
#include 
using namespace std;

const int MAXN = 1000005;
int s[MAXN], dp[MAXN], temp[MAXN];

void DP(int m, int n) {
    memset(dp, 0, sizeof(dp));
    memset(temp, 0, sizeof(temp));
    
    for(int i = 1; i <= m; i++) {
        int max_val = -0x3f3f3f3f;  // 負無窮初始化
        for(int j = i; j <= n; j++) {
            dp[j] = max(dp[j-1] + s[j], temp[j-1] + s[j]);
            temp[j-1] = max_val;        // 保存前j-1的最大值
            if(max_val < dp[j]) max_val = dp[j];  // 更新最大值
        }
    }
    cout << max_val << endl;
}

int main() {
    int n, m;
    while(scanf("%d%d", &m, &n) != EOF) {
        for(int i = 1; i <= n; i++) scanf("%d", &s[i]);
        DP(m, n);
    }
    return 0;
}

複雜度分析

• 時間複雜度：O(M×N) — 雙重循環，每層線性掃描
• 空間複雜度：O(N) — 三個長度N的一維數組

關鍵優化細節

1. 輸入優化：使用scanf而非cin，大數據下速度提升數倍
2. 負無窮初始化：-0x3f3f3f3f避免整數溢出，比-999999999更安全
3. temp更新順序：先用舊max_val更新temp[j-1]，再用dp[j]更新max_val，保證狀態正確性
4. 下標設計：數組從1開始，符合問題語義，減少邊界錯誤

擴展思考

若需輸出具體子段位置，可引入前驅數組記錄決策路徑；若M較小可考慮分治優化至O(N log N)；對於在線查詢版本，可研究線段樹維護DP矩陣的技術。