牛客劍指 Offer：數組連續子向量最大和（最大子數組和）

題目描述

給定整型數組（含正負數），求連續子數組的最大和。例如 {6, -3, -2, 7, -15, 1, 2, 2} 最大和為 8（前 4 個元素）。

經典解法：動態規劃 / Kadane 算法

狀態定義：dp[i] 表示以 a[i] 結尾的最大子數組和。
轉移方程：dp[i] = max(a[i], dp[i-1] + a[i])。
答案：max(dp[i])。
可優化為 O(1) 空間，只保留當前最大結尾和與全局最大和。

C++ 代碼實現（優化版）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxSubArraySum(const vector<int>& a) {
    if (a.empty()) return 0;
    int curMax = a[0], globalMax = a[0];
    for (size_t i = 1; i < a.size(); ++i) {
        curMax = max(a[i], curMax + a[i]);
        globalMax = max(globalMax, curMax);
    }
    return globalMax;
}

int main() {
    vector<int> a = {6, -3, -2, 7, -15, 1, 2, 2};
    cout << maxSubArraySum(a) << endl; // 輸出 8
    return 0;
}

原文代碼分析

原文提供了一種 O(n²) 的暴力前綴和方法（雙層循環枚舉所有子數組），雖然在牛客上通過，但效率低下。上述 Kadane 算法將時間複雜度從 O(n²) 降至 O(n)，空間從 O(n) 降至 O(1)，是標準最優解。

擴展：輸出最大子數組區間

pair<int, int> maxSubArrayRange(const vector<int>& a) {
    int curMax = a[0], globalMax = a[0];
    int curStart = 0, bestL = 0, bestR = 0;
    for (int i = 1; i < a.size(); ++i) {
        if (curMax + a[i] < a[i]) {
            curMax = a[i];
            curStart = i;
        } else {
            curMax += a[i];
        }
        if (curMax > globalMax) {
            globalMax = curMax;
            bestL = curStart;
            bestR = i;
        }
    }
    return {bestL, bestR};
}