[LeetCode解題攻略] 53. Maximum Subarray

題目描述

這道題是 LeetCode 的經典題之一，要求我們找出 一個子陣列，使其和最大，並返回這個最大和的數值。

• 給定一個數組 nums，找到一個具有最大和的 子陣列（subarray），並返回其最大和。

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

這表示我們要找 最優解法，因為 nums 可能非常大，暴力解法的 O(n²) 可能會超時。

範例

範例 1：

輸入: nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出: 6
解釋： 最大子陣列為 [4, -1, 2, 1]，其和為 4 + (-1) + 2 + 1 = 6。

範例 2：

輸入: nums = [1]
輸出: 1
解釋： 只有一個數，所以答案就是 1。

範例 3：

輸入: nums = [5,4,-1,7,8]
輸出: 23
解釋： 最大子陣列為 [5, 4, -1, 7, 8]，其和為 23。

解題思路

思路 1：暴力解法

• 遍歷所有可能的子陣列，計算總和，找出最大值。
• 這種方法的時間複雜度為 O(n²)，不可行。

思路 2：Kadane's Algorithm（動態規劃）

• 使用 動態規劃（Dynamic Programming），透過 dp[i] 存儲 以 nums[i] 為結尾的最大子陣列和，然後找出最大值。
• 這種方法的時間複雜度為 O(n)，適合大數據量。

思路 3：分治法（Divide and Conquer）

• 運用遞迴方式，將陣列分成左、右兩部分，然後合併解決。
• 這種方法的時間複雜度為 O(n log n)。

解法一：暴力枚舉

思路

1. 遍歷 nums 的所有 子陣列，計算其總和。
2. 找出 最大的總和 並返回。

程式碼

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sum = float('-inf')
        n = len(nums)
        for i in range(n):
            current_sum = 0
            for j in range(i, n):
                current_sum += nums[j]
                max_sum = max(max_sum, current_sum)
        return max_sum

時間與空間複雜度

• 時間複雜度：O(n²)
• • 內部雙層迴圈，每次都要計算新的子陣列總和，會超時。
• 空間複雜度：O(1)
• • 只使用了 max_sum 和 current_sum，額外空間需求為 O(1)。

解法二：Kadane's Algorithm（動態規劃）

思路

1. 使用 current_sum 來記錄 當前以 nums[i] 為結尾的最大子陣列和。
2. 如果 current_sum 變成負數，則 從下一個數字重新開始（因為負數會降低總和）。
3. 同時維護 max_sum，確保記錄到最大的結果。

程式碼

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sum = nums[0]
        current_sum = nums[0]
        for i in range(1, len(nums)):
            current_sum = max(nums[i], current_sum + nums[i])
            max_sum = max(max_sum, current_sum)
        return max_sum

時間與空間複雜度

• 時間複雜度：O(n)
• • 只需一次遍歷 nums，每個元素只計算一次。
• 空間複雜度：O(1)
• • 只使用了 current_sum 和 max_sum，不需要額外空間。

解法三：分治法（Divide and Conquer）

思路

1. 拆分陣列，分為 左部分、右部分、橫跨中點的最大子陣列。
2. 遞迴計算左、右部分的最大子陣列和。
3. 計算包含中點的最大子陣列和（透過從中點開始向左、向右擴展）。
4. 返回三者之間的最大值。

程式碼

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        def divide_and_conquer(left, right):
            if left == right:
                return nums[left]

            mid = (left + right) // 2
            left_sum = divide_and_conquer(left, mid)
            right_sum = divide_and_conquer(mid + 1, right)

            cross_sum = find_cross_sum(nums, left, right, mid)

            return max(left_sum, right_sum, cross_sum)

        def find_cross_sum(nums, left, right, mid):
            left_max = float('-inf')
            right_max = float('-inf')

            sum_temp = 0
            for i in range(mid, left - 1, -1):
                sum_temp += nums[i]
                left_max = max(left_max, sum_temp)

            sum_temp = 0
            for i in range(mid + 1, right + 1):
                sum_temp += nums[i]
                right_max = max(right_max, sum_temp)

            return left_max + right_max

        return divide_and_conquer(0, len(nums) - 1)

時間與空間複雜度

• 時間複雜度：O(n log n)
• • 由於每次遞迴都將問題劃分為兩半，類似於歸併排序，因此時間複雜度為 O(n log n)。
• 空間複雜度：O(log n)
• • 由於使用遞迴，每層遞迴佔用 O(log n) 的空間。

結論

這題是一道經典的動態規劃問題，適合用 Kadane's Algorithm 來解，因為它的 O(n) 時間複雜度 適合大數據量。