最大子序和dp

最大子序和（Maximum Subarray Problem）是一個經典的動態規劃問題。給定一個整數數組，找到一個子數組，使其元素的和最大。

動態規劃的解決方案通常使用一個數組來存儲每個子數組的最大和，這個數組被稱為最大子序和數組。我們可以使用以下動態規劃方程來計算這個數組：

設 maxSubArray[i] 為長度為 i 的子數組的最大和，我們可以定義以下狀態轉移方程：

maxSubArray[i] = max(maxSubArray[i-1] + arr[i], arr[i])

其中 arr[i] 是數組的第 i 個元素。

初始條件是 maxSubArray[0] = arr[0]，表示長度為 0 的子數組的最大和就是數組中的第一個元素。

我們可以通過以下偽代碼來實現這個動態規劃算法：

function maxSubArray(arr):
    maxSubArray[0] = arr[0]
    for i from 1 to length(arr):
        maxSubArray[i] = max(maxSubArray[i-1] + arr[i], arr[i])
    return maxSubArray

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

在實際套用中，我們通常不需要存儲整個最大子序和數組，我們只需要找到最大子序和本身。這可以通過在遍歷數組的同時維護兩個變數來實現：一個變數 curMax 用來存儲當前子數組的最大和，另一個變數 globalMax 用來存儲到目前為止所有子數組的最大和。我們可以使用以下偽代碼來實現這個算法：

function findMaxSubArray(arr):
    curMax = 0
    globalMax = arr[0]
    for i from 1 to length(arr):
        curMax = max(curMax + arr[i], arr[i])
        globalMax = max(globalMax, curMax)
    return globalMax

這個算法的時間複雜度和空間複雜度都是 O(n)。