題目描述
這道題是 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)。
解法一：暴力枚舉
思路
- 遍歷
nums的所有 子陣列，計算其總和。 - 找出 最大的總和 並返回。
程式碼
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（動態規劃）
思路
- 使用
current_sum來記錄 當前以nums[i]為結尾的最大子陣列和。 - 如果
current_sum變成負數，則 從下一個數字重新開始（因為負數會降低總和）。 - 同時維護
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）
思路
- 拆分陣列，分為 左部分、右部分、橫跨中點的最大子陣列。
- 遞迴計算左、右部分的最大子陣列和。
- 計算包含中點的最大子陣列和（透過從中點開始向左、向右擴展）。
- 返回三者之間的最大值。
程式碼
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) 時間複雜度 適合大數據量。
