LeetCode 熱題 100 | 53. 最大子數組和

大家好，今天我們來解決一道經典的算法題——最大子數組和。這道題在 LeetCode 上被標記為中等難度，要求我們找出一個具有最大和的連續子數組，并返回其最大和。下面我將詳細講解解題思路，并附上 Python 代碼實現。

---

題目描述

給定一個整數數組 nums，請你找出一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。

示例：

輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出：6
解釋：連續子數組 [4,-1,2,1] 的和最大，為 6。

---

解題思路

這道題的核心是找到一個連續子數組，使得其和最大。我們可以使用 動態規劃 或 分治法 來解決這個問題。

核心思想

1. 動態規劃：

   • 定義 dp[i] 表示以 nums[i] 結尾的子數組的最大和。
   • 狀態轉移方程：
     dp[i] = max(dp[i-1] + nums[i], nums[i])
   • 最終結果是 dp 數組中的最大值。

2. 分治法：

   • 將數組分成左右兩部分，分別求解左右部分的最大子數組和。
   • 求解跨越中間的最大子數組和。
   • 返回左部分、右部分和跨越中間的最大值。

---

代碼實現

方法 1：動態規劃

def maxSubArray(nums):""":type nums: List[int]:rtype: int"""n = len(nums)dp = [0] * ndp[0] = nums[0]  # 初始化 dp[0]max_sum = dp[0]  # 初始化最大和for i in range(1, n):dp[i] = max(dp[i-1] + nums[i], nums[i])  # 狀態轉移max_sum = max(max_sum, dp[i])  # 更新最大和return max_sum

方法 2：分治法

def maxSubArray(nums):""":type nums: List[int]:rtype: int"""def divide_and_conquer(left, right):if left == right:return nums[left]mid = (left + right) // 2# 分別求解左右部分的最大子數組和left_max = divide_and_conquer(left, mid)right_max = divide_and_conquer(mid + 1, right)# 求解跨越中間的最大子數組和left_sum = nums[mid]right_sum = nums[mid + 1]temp = left_sumfor i in range(mid - 1, left - 1, -1):temp += nums[i]left_sum = max(left_sum, temp)temp = right_sumfor i in range(mid + 2, right + 1):temp += nums[i]right_sum = max(right_sum, temp)cross_max = left_sum + right_sum# 返回左部分、右部分和跨越中間的最大值return max(left_max, right_max, cross_max)return divide_and_conquer(0, len(nums) - 1)

---

代碼解析

動態規劃

1. 初始化：

   • dp[0] 表示以 nums[0] 結尾的子數組的最大和，初始化為 nums[0]。
   • max_sum 初始化為 dp[0]。

2. 狀態轉移：

   • 對于每個 i，計算 dp[i]，表示以 nums[i] 結尾的子數組的最大和。
   • 如果 dp[i-1] + nums[i] 比 nums[i] 大，則繼續擴展子數組；否則，從 nums[i] 重新開始。

3. 更新最大和：

   • 每次計算 dp[i] 后，更新 max_sum。

4. 返回結果：

   • 返回 max_sum。

分治法

1. 遞歸終止條件：

   • 如果 left == right，返回 nums[left]。

2. 遞歸求解左右部分：

   • 分別遞歸求解左部分和右部分的最大子數組和。

3. 求解跨越中間的最大子數組和：

   • 從中間向左右擴展，求解跨越中間的最大子數組和。

4. 返回最大值：

   • 返回左部分、右部分和跨越中間的最大值。

---

復雜度分析

• 時間復雜度：

  • 動態規劃：O(n)，其中 n 是數組的長度。我們只需要遍歷數組一次。
  • 分治法：O(n log n)，每次遞歸將數組分成兩部分，遞歸深度為 log n，每層需要 O(n) 的時間求解跨越中間的最大子數組和。

• 空間復雜度：

  • 動態規劃：O(n)，需要額外的 dp 數組。
  • 分治法：O(log n)，遞歸調用棧的深度為 log n。

---

示例運行

示例 1

# 輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(maxSubArray(nums))  # 輸出: 6

示例 2

# 輸入：nums = [1]
nums = [1]
print(maxSubArray(nums))  # 輸出: 1

示例 3

# 輸入：nums = [5,4,-1,7,8]
nums = [5, 4, -1, 7, 8]
print(maxSubArray(nums))  # 輸出: 23

---

總結

通過動態規劃或分治法，我們可以高效地找到最大子數組和。動態規劃的時間復雜度為 O(n)，是最優的解法；分治法的時間復雜度為 O(n log n)，適合理解分治思想。希望這篇題解對你有幫助！如果還有其他問題，歡迎繼續提問！

關注我，獲取更多算法題解和編程技巧！