Maximum Subarray最大子陣列
分治版與 Kadane 線性版的對照。
用在：股票最佳買賣區間、訊號分析
01為什麼需要它
有一年份的每日漲跌。想知道如果只能買一次賣一次，哪一天買、哪一天賣最賺。試每一對買賣日是 O(n²)，250 天還好，十年的分鐘線就撐不住。
為什麼用它每日漲跌加起來就是持有期間的獲利，問題變成「連續一段加總最大」。分治把它切半，答案不是在左半、就在右半、不然就跨過中線，O(n log n)。Kadane 再壓到 O(n)。
感測器回傳一串數值，扣掉基準線後有正有負。要找出「訊號最集中」的連續時段，也就是加總最大的區間。
為什麼用它和股票是同一題。Kadane 一路掃過去，遇到累積變負就重新開始，因為帶著負的前綴只會拖累後面。
線段樹要支援「任意區間的最大子陣列和」，每次查詢不能重掃整段。
為什麼用它分治版合併左右兩半的方式（左半最佳、右半最佳、左後綴加右前綴）正是線段樹節點要存的四個值。這一課先把合併的邏輯練熟，之後就是把它放進樹裡。
看到這些關鍵字就想到它：連續子陣列、加總最大、最佳買賣區間、一段最強的訊號、可以切半再合併。
02核心概念
最大子陣列：在一串有正有負的數裡，找連續一段使加總最大。暴力枚舉所有 (l, r) 是 O(n²)，用前綴和也只是把內層加總變 O(1)，枚舉本身還是 n²。
分治的觀察是：把陣列從中間切開，答案的區間只有三種位置，完全在左半、完全在右半、跨過中線。前兩種遞迴解決。第三種一定包含 mid 和 mid+1，所以它等於「以 mid 結尾的最大後綴」加「從 mid+1 開始的最大前綴」，各掃一次 O(n) 就能算出。三者取最大。遞迴式 T(n) = 2T(n/2) + n，由 Master Theorem 得 O(n log n)，空間是遞迴深度 O(log n)。
Kadane 換一個角度：定義 cur 為「以第 i 個元素結尾的最大和」。要嘛把 a[i] 接在前一段後面（cur + a[i]），要嘛從 a[i] 重新開始，取大的那個。等價地說，前面累積若是負的，帶著只會拖累，直接丟掉。整體答案是所有 cur 的最大值。一次掃描 O(n)、O(1) 空間。這其實是一維 DP，之後會在 DP 主題再遇到它。
兩者的取捨：Kadane 更快也更短，面試寫它。分治的價值在合併的形狀：一個區段的資訊只要記「總和、最大前綴、最大後綴、最大子段」四個數，兩個相鄰區段就能 O(1) 合併，這正是線段樹處理區間最大子陣列的做法。常見錯誤：全是負數時答案是最大的那個負數而不是 0，所以 best 要初始化成 a[0] 而不是 0。
03演算法步驟
- 1分治：
solve(lo, hi)回傳該區間的最大子陣列和。若lo == hi，回傳a[lo]。 - 2取
mid，遞迴求left = solve(lo, mid)與right = solve(mid+1, hi)。 - 3跨中線：從 mid 往左累加，記錄最大值
bestL；從 mid+1 往右累加，記錄最大值bestR。跨中線的答案是bestL + bestR。 - 4回傳
max(left, right, bestL + bestR)。每層 O(n)，共 log n 層。 - 5Kadane：
cur = max(a[i], cur + a[i])，best = max(best, cur)，從a[0]開始初始化，一次掃完。
04互動示範
八天的漲跌。前半段是分治：遞迴樹上藍色是正在處理的區間，綠色是已解出的；陣列裡黃色是跨中線掃描的範圍，綠色是這一層的答案區間。分治做完後，同一串步驟接著跑 Kadane：陣列裡黃色是 cur 對應的區間，綠色是目前的 best，看它怎麼用兩個變數掃一遍就得到同樣的答案。
05程式碼
分治版與 Kadane 版並列，加上一個回傳區間位置的變形，股票題要的「哪天買哪天賣」就是它。
# 最大子陣列（LeetCode 53）：分治版
# 答案只有三種可能：全在左半、全在右半、跨過中線
def max_subarray_dc(a):
def solve(lo, hi):
if lo == hi:
return a[lo] # 單一元素
mid = (lo + hi) // 2
left = solve(lo, mid) # 全在左半
right = solve(mid + 1, hi) # 全在右半
# 跨中線：從 mid 往左的最大後綴 + 從 mid+1 往右的最大前綴
s, best_l = 0, float("-inf")
for i in range(mid, lo - 1, -1):
s += a[i]
best_l = max(best_l, s)
s, best_r = 0, float("-inf")
for i in range(mid + 1, hi + 1):
s += a[i]
best_r = max(best_r, s)
return max(left, right, best_l + best_r) # 三者取最大
return solve(0, len(a) - 1)
# Kadane：cur 是「以 i 結尾」的最大和，負的就丟掉重來
def max_subarray_kadane(a):
cur = best = a[0]
for x in a[1:]:
cur = max(x, cur + x) # 接上去，或從 x 重新開始
best = max(best, cur)
return best
# 變形：同時回傳區間 [l, r]
def max_subarray_range(a):
cur, best = a[0], a[0]
start, l, r = 0, 0, 0
for i in range(1, len(a)):
if cur < 0:
cur, start = a[i], i # 重新開始
else:
cur += a[i]
if cur > best:
best, l, r = cur, start, i
return best, l, r
if __name__ == "__main__":
a = [-2, 1, -3, 4, -1, 2, 1, -5]
print(max_subarray_dc(a), max_subarray_kadane(a), max_subarray_range(a)) # 6 6 (6, 3, 6)06練習題
- LeetCode 121Best Time to Buy and Sell Stock（把價格轉成每日漲跌）Easy
- LeetCode 53Maximum Subarray（分治和 Kadane 各寫一次）Medium
- LeetCode 152Maximum Product Subarray（同時追蹤最大與最小）Medium
- LeetCode 918Maximum Sum Circular Subarray（總和減最小子陣列）Medium
- LeetCode 1186Maximum Subarray Sum with One DeletionMedium
- LeetCode 363Max Sum of Rectangle No Larger Than K（二維壓成一維）Hard