題目出處
難度
Easy
題目分類
Array, Divide and Conquer, Dynamic Programming
2026-07-23 三刷
個人範例程式碼 - 三刷 (2026/07/23)
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
best_ending_here = best_so_far = nums[0]
for i in range(1, len(nums)):
# add best sums before will be better or not (then just take current)?
best_ending_here = max(best_ending_here + nums[i], nums[i])
best_so_far = max(best_so_far, best_ending_here)
return best_so_far
算法說明
- best_ending_here 比較包含這個的最大，兩種可能：
- 前面總和+自己 比較大
- 自己 比較大（發生於前面總和為負的情況）
這題基本上如果恆正只要一直加就能最大，只需要用以上方式處理有「前方總和有負」（不是單純此值為負）出現的情況
- best_so_far 紀錄一直以來的最大
Time Complexity
O(n)
Space Complexity
O(1)
Boundary conditions
i = 1, best 為 nums[0], 拿去當預設結果
i = 2, best 可能為 nums[0], nums[1], nums[0]+nums[1], for loop 需要從 1 開始跑
2022-04-28 二刷
個人範例程式碼 - 2022/4/28
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
if not nums:
return 0
current_max_with_this = [nums[0]]
for i in range(1, len(nums)):
current_max_with_this.append(max(current_max_with_this[i-1]+nums[i], nums[i]))
return max(current_max_with_this)
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
算法說明
建一個新的 array，記錄"包含自己"的當前最大用
當前最大 = max(當前數字, 當前數字+到前一個之前最大)
input handling
如果 input not nums (沒有數字)，return 0
Boundary conditions
for 控制範圍
2022-02-24 一刷
個人範例程式碼 - 2022/2/24
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
dp = [] # dp = the biggest answer 'include me'
for i in range(len(nums)):
if i == 0:
dp.append(nums[i])
else:
bigger = max(nums[i], nums[i]+dp[i-1])
dp.append(bigger)
return max(dp)
說明
這題我使用的是 DP 的解法，
我宣告一個 DP 來儲存「包含自己的」時最好的答案。
換句話說，我將題目拆解成到「包含每一個 index 的當下」 都是一個小題目，將題目的答案儲存進 dp 中。
注意是「包含自己」的最好答案，也就是說，我們只需要比較「自己」與「dp(n-1)+自己」誰比較大。
DP 裡面都是「一定要包含自己的最佳解」，而不是「全域的最佳解」。
所以假設原來的題目變成：
nums = [1,2,-1,4]
dp = [1,3,2,6]
2 就是因為一定要包含「-1」，我們只有「-1」跟「-1+‘包含前一個’的最大」誰比較大。