題幹與適用場景
輸入長度為 n 的整數陣列，陣列首尾相連；連續子陣列可以跨越尾部與首部，但不能重複使用同一位置。回傳非空子陣列的最大和。面試中常要求從普通 Kadane 演算法推導環形變體，並解釋全負陣列為何不能直接用 total - minSum。
面試官考察點
- 能否把環形答案拆成「不跨邊界」與「跨邊界」兩類。
- 能否用最大子陣列和與最小子陣列和的互補關係避免複製陣列。
- 能否保留非空約束，處理全負陣列、單一元素與整數範圍。
回答前需要釐清的問題
- 子陣列是否必須非空？本題必須非空，因此全負陣列要回傳最大負數。
- 每個位置能否使用兩次？不能；跨邊界區間等價於刪除一個非空中間區間。
- 只需要總和還是也要回傳起止位置？本題只回傳總和；若要位置，需要額外記錄邊界並處理跨界映射。
30 秒回答框架
我把答案分成兩類：不跨邊界時就是普通最大子陣列和；跨邊界時等於總和減去一個非空最小子陣列和。一次掃描同時維護最大和、最小和與總和。如果最小子陣列覆蓋整個陣列，total - minSum 會代表空子陣列，必須回傳普通最大和。這樣時間 O(n)、額外空間 O(1)。
分步驟深入解答
1. 推導兩類答案
不跨邊界的最佳區間由 Kadane 演算法得到。跨邊界區間由陣列後綴加前綴組成，它的補集是陣列中間的一段非空連續區間，因此其和為 total - minSubarray。兩類取最大值即可涵蓋所有合法區間。
2. 維護 Kadane 不變量
掃描到元素 x 時，普通最大和維護「以目前位置結尾的最大和」；最小和維護「以目前位置結尾的最小和」。更新順序可以先用舊前綴計算新候選，再更新前綴極值。初始化時最大和為負無限、最小和為正無限，確保單一負值陣列不會被當成空答案。
3. 處理全負陣列
若所有元素為負，最小子陣列就是整個陣列，total - minSubarray = 0，這代表空區間，違反題意。此時直接回傳普通 Kadane 的最大和。判斷可以寫成「最大和為負」，也可以記錄最小區間是否覆蓋整個陣列；前者更簡潔。
4. 程式與複雜度
from typing import List
class Solution:
def maxSubarraySumCircular(self, nums: List[int]) -> int:
total = 0
current_max = current_min = 0
best_max = float("-inf")
best_min = float("inf")
for value in nums:
total += value
current_max = max(value, current_max + value)
best_max = max(best_max, current_max)
current_min = min(value, current_min + value)
best_min = min(best_min, current_min)
if best_max < 0:
return int(best_max)
return int(max(best_max, total - best_min))每個元素只存取一次，時間複雜度 O(n)，額外空間複雜度 O(1)。若整數範圍可能超過語言的機器整數，total 與中間和要使用更寬型別。
5. 關鍵反例與驗證
[5,-3,5] 的跨界答案是 5 + 5 = 10。[-3,-2,-3] 不能回傳 0，必須回傳 -2。[1,-2,3,-2] 的普通答案為 3，跨界候選不會超過它。測試還應涵蓋一個元素、全正、首尾相連後等價於整段陣列，以及最大數值相加接近整數上限。
高品質示範回答
「我先區分區間是否跨越尾首。不跨界就是 Kadane 的最大子陣列和；跨界區間可以看成刪除一段中間的非空最小子陣列，所以候選是總和減最小和。我在一次遍歷裡同時維護最大和、最小和與總和。全負時最小區間會等於整個陣列，補集變成空區間，因此直接回傳普通最大和。這個實作每個元素存取一次，時間 O(n)、空間 O(1)，並用單一元素和接近整數邊界的案例檢查非空約束與溢位。」
常見錯誤
- 複製陣列後跑普通 Kadane → 可能重複使用同一位置 → 限制視窗長度或使用互補區間推導。
- 無條件回傳
total - minSum→ 全負陣列得到空區間 0 → 先處理最大和為負的分支。 - 把最小子陣列允許為空 → 跨界公式失去非空補集約束 → 最小 Kadane 也必須從真實元素開始。
- 只給 O(n) 結論不解釋不變量 → 無法證明邊界涵蓋完整 → 明確兩類區間和每個狀態的定義。
追問及應對
如果要求回傳區間起止位置怎麼辦？
同時記錄最大和與最小和的起止索引。跨界答案的區間是最小區間補集，可能表示為 [minEnd+1,n-1] 與 [0,minStart-1] 兩段；需要規定回傳兩個區間還是映射成環上的起點與長度。
如果允許空子陣列，程式如何改變？
最大答案至少為 0，初始化與轉移可以允許目前和歸零；但這改變了全負陣列的語義。應先確認題意，再決定是否使用允許空區間的 Kadane。
如果陣列是動態串流，能否 O(1) 更新？
單端追加可以維護前綴、後綴和及相關摘要，但刪除任意舊元素會破壞最小或最大區間資訊，通常需要線段樹或分塊摘要。先釐清更新方向、查詢頻率與是否允許近似，再選擇資料結構。
如果要求恰好長度 k 呢？
互補公式不能直接套用，因為補集長度也被固定約束。可把陣列視為長度 2n 的序列，用滑動視窗或前綴和維護長度為 k 的區間，並限制視窗不超過 n；複雜度與 k 和查詢模式相關。