最大子列和

最大子列和問題（Maximum Subarray Problem）是一個經典的動態規劃問題。給定一個整數數組，找到一個連續子列，其總和最大。如果數組中所有的元素都是負數，那麼最大的子列和為0。

這個問題可以通過動態規劃來解決。我們定義一個數組dp，其中dp[i]表示以nums[i]結尾的最大子列和。我們可以使用如下的動態規劃方程來計算dp：

dp[i] = max(dp[i - 1] + nums[i], nums[i])

初始時，dp[0] = nums[0]。

我們可以通過遍歷數組來計算dp，然後返回dp中的最大值。下面是一個簡單的實現：

def maxSubArray(nums):
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]
    for i in range(1, n):
        dp[i] = max(dp[i - 1] + nums[i], nums[i])
    return max(dp)

# 測試
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(maxSubArray(nums))  # 輸出應該是 6

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