最大子串和

最大子串和問題是一個經典的計算機科學問題，它要求在一個給定的整數數組中找到一個連續子串，其總和最大。這個問題有很多套用，例如在股票市場的分析中，可以用來找到一段時期內股票價格的最大漲幅。

這個問題可以用動態規劃來解決。動態規劃算法的基本思想是，通過存儲子問題的解來避免重複計算。在這個問題中，我們可以定義一個子問題，即對於數組中的每個元素，找到其結尾的最大子串和。

我們可以使用一個數組來存儲這些子問題的答案。這個數組稱為累積和數組，它的第 i 個元素包含從數組開始到第 i 個元素的最大子串和。我們可以通過以下方式計算這個數組：

1. 累積和數組的第 0 個元素是數組第 0 個元素的值。
2. 對於 i 從 1 到數組長度減 1 的每個元素，累積和數組的第 i 個元素是數組第 i 個元素加上累積和數組的第 i - 1 個元素的最大值。

一旦我們計算出了累積和數組，我們就可以通過遍歷這個數組來找到最大子串和。

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

def max_subarray_sum(arr):
    n = len(arr)
    # 創建累積和數組
    prefix_sums = [0] * n
    prefix_sums[0] = arr[0]

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

    # 找到最大子串和
    max_sum = prefix_sums[0]
    for i in range(n):
        max_sum = max(max_sum, prefix_sums[i])

    return max_sum

# 示例
arr = [1, -2, 3, 10, -4, 7, 2, -5]
print(max_subarray_sum(arr))  # 輸出應該是 17

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