最大子數組和

最大子數組和（Maximum Subarray Problem）是一個經典的動態規劃問題，它的目標是在一個給定的數組中找到連續子數組，其和最大。

例如，給定數組 [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]，其中最大的子數組和是 62，這個子數組是 [20, -3, -16, -23, 18, 20]。

解決這個問題的動態規劃算法如下：

1. 定義狀態：我們定義狀態 f[i] 表示以 a[i] 為最後一個元素的最大子數組和。

2. 狀態轉移方程：為了找到 f[i]，我們需要考慮以 a[i-1] 為最後一個元素的子數組和與 a[i]。如果 f[i-1] + a[i] 更大，那麼 f[i] = f[i-1] + a[i]；否則，f[i] = a[i]。

3. 初始狀態：f[0] = a[0]。

4. 遞推：使用狀態轉移方程計算 f[1], f[2], ..., f[n-1], f[n]。

5. 返回最大值：返回所有 f[i] 中的最大值。

以下是一個簡單的Python實現：

def maxSubArray(arr):
    n = len(arr)
    # 初始化 f[0]
    f = [0] * n
    f[0] = arr[0]

    for i in range(1, n):
        f[i] = max(f[i-1] + arr[i], arr[i])

    # 返回最大值
    return max(f)

# 示例
arr = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
print(maxSubArray(arr))  # 輸出: 62

這個算法的時間複雜度和空間複雜度都是 O(n)，其中 n 是數組的大小。