最大子序和

最大子序和（Maximum Subsequence Sum）是一個經典的動態規劃問題。給定一個整數序列，最大子序和問題是要找到該序列中長度大於0的子序列，其和最大。

例如，對於序列[−2, 11, −4, 13, −5, −2]，最大的子序列和是11 + 13 = 24，對應的子序列是[11, 13]。

動態規劃的解決方案如下：

設f[i]表示以第i個元素結尾的最大子序列和，那麼有狀態轉移方程：

f[i] = max(f[i - 1], 0) + a[i]

其中a[i]是序列中的第i個元素。

初始條件是f[0] = 0。

時間複雜度為O(n)，空間複雜度也是O(n)，因為需要存儲整個dp數組。

另外，對於這個問題，有一個更高效的解決方案，即Kadane's algorithm，它可以線上性時間內解決最大子序列和問題。Kadane's algorithm的偽代碼如下：

max_sum = current_sum = 0
for i from 0 to length(a) - 1:
    if current_sum < 0:
        current_sum = 0
    else:
        current_sum += a[i]
    max_sum = max(max_sum, current_sum)
return max_sum

時間複雜度為O(n)，空間複雜度為O(1)，因為它只使用了常數空間的額外變數。