LeetCode Maximum Subarray：最大子數組和 — 動態規劃 / 貪心 (Kadane 算法)

題目描述

給定整數數組（含負數），找到和最大的連續子數組，返回其和。

範例： [-2,1,-3,4,-1,2,1,-5,4] → 6 (子數組 [4,-1,2,1])

解題思路：Kadane 算法

維護 current 為以當前元素結尾的最大子數組和，maxSum 為全局最大值。遞推：
current = max(nums[i], current + nums[i])
maxSum = max(maxSum, current)

參考代碼 (Python)

class Solution:
    def maxSubArray(self, nums):
        if not nums: return 0
        cur = max_sum = nums[0]
        for x in nums[1:]:
            cur = max(x, cur + x)
            max_sum = max(max_sum, cur)
        return max_sum

複雜度分析

• 時間：O(n) —— 單次遍歷。
• 空間：O(1)。