最大子序列之和

最大子序列之和問題是一個經典的動態規劃問題。給定一個整數序列，我們要找到其中的一段連續子序列，其和最大。

例如，給定序列 {-2, 11, -4, 13, -5, -2}，最大的子序列和可以通過選擇序列 {11, -4, 13} 得到，其和為 11 + (-4) + 13 = 20。注意，我們不能選擇不連續的子序列，例如 {-2, 11, -4} 是不允許的。

動態規劃算法通過定義子問題來解決問題。在這個問題中，我們可以定義子問題為：對於序列的每一部分，其最大子序列和是多少。通過解決這些子問題，我們可以構建出整個序列的最大子序列和。

動態規劃算法的步驟如下：

  1. 定義狀態：我們定義狀態 DP[i] 表示以序列第 i 個元素結尾的最大子序列和。

  2. 確定狀態轉移方程：我們需要確定如何從 DP[i-1]（以序列第 i-1 個元素結尾的最大子序列和）計算出 DP[i]。如果序列的第 i 個元素比前一個子序列的最後一個元素大，那麼我們可以通過將當前元素加到前一個子序列上得到新的最大子序列和。否則，我們應該忽略當前元素，因為加上它會減小子序列的和。

  3. 初始條件：我們需要一個初始狀態來開始計算。通常，我們定義 DP[0] 為序列中前幾個元素的最大子序列和（如果序列為空，則為 0）。

  4. 計算最大子序列和：我們從序列的最後一個元素開始，向前遞歸地計算每個 DP[i]，直到 DP[0] 被計算出來。

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

def max_sub_seq_sum(arr):
    n = len(arr)
    # 定義狀態
    dp = [float('-inf')] * n  # 初始化為負無窮大
    dp[0] = arr[0]  # 第一個元素就是以它結尾的最大子序列和

    for i in range(1, n):
        # 狀態轉移方程
        dp[i] = max(dp[i-1] + arr[i], arr[i])

    # 返回最大子序列和
    return dp[-1]

# 示例
arr = [-2, 11, -4, 13, -5, -2]
print(max_sub_seq_sum(arr))  # 輸出應該是 20

這個算法的時間複雜度和空間複雜度都是 O(n)，其中 n 是序列的長度。