程式面試：刪除至多一個元素後的最大子陣列和
面試官考察點
給定整數陣列，回傳刪除至多一個元素後得到的非空連續子陣列最大和。刪除操作最多一次，也可以不刪除；刪除後剩餘元素仍必須來自同一個連續區間。
約束與邊界
- 陣列至少包含一個元素，元素可為負數、零或正數。
- 刪除後不能得到空陣列。
- 需要說明是否允許刪除區間端點；端點刪除等同於不把該元素納入區間。
- 目標是單次掃描，不能枚舉刪除位置與左右區間。
把「是否刪除」變成狀態
維護 keep：以目前位置結尾且尚未刪除元素的最大和；維護 drop：以目前位置結尾且已經刪除一次的最大和。讀到 x 時，keep 在重新開始與延長之間取最大值；drop 在刪除目前元素與延長已刪除狀態之間取最大值。
區分結果狀態與中間狀態
答案必須同時考慮 keep 與 drop，因為最佳解可能從未刪除狀態結束，也可能刪除負數後結束。初始化不能把 drop 設為零，否則會允許空子陣列或隱式刪除不存在的元素。
解釋線性複雜度
每個元素只更新兩個常數狀態，時間複雜度 O(n)，額外空間 O(1)。正確性來自狀態覆蓋：任意以目前位置結尾的合法區間，要麼尚未刪除，要麼已刪除一次，且兩類狀態都保留最大和。
回答前需要釐清的問題
- 「刪除至多一個」是否包含不刪除？若改成必須刪除，答案和單元素陣列邊界會改變。
- 刪除後是否必須非空？若允許空陣列，結果可能被錯誤初始化為零。
- 輸入整數是否可能溢出 32 位？這決定累加型別與測試範圍。
30 秒回答框架
「我維護兩個以目前位置結尾的狀態：keep 表示還沒刪，drop 表示已刪一次。讀到 x 時，keep 取重新開始或延長；drop 取刪除 x 或延長舊的 drop。答案是全程 keep 與 drop 的最大值，初始化用首元素避免全負陣列得到零，時間 O(n)、空間 O(1)。 」
分步驟深入解答
設上一位置狀態為 keepPrev 與 dropPrev。更新公式為：
keep = max(x, keepPrev + x)
drop = max(dropPrev + x, keepPrev)第二行的 keepPrev 表示刪除目前元素，舊區間至少包含一個元素；dropPrev + x 表示刪除動作已發生，再把目前元素接上。先保存舊值或使用暫存變數，避免更新 keep 後污染 drop 的轉移。
若陣列只有一個元素，keep 是該元素，drop 不應被當成合法空區間。實作可把 drop 初始化為負無窮，並從第二個元素開始更新；也可以在首元素建立「未刪除」與「刪除首元素」的明確語意，但必須保證非空約束。
高品質示範回答
「我把問題拆成兩個 DP 狀態。keep 是目前索引結尾、沒有刪除的最大和，drop 是已刪除一個元素的最大和。對每個 x，先用舊的 keep 和 drop 計算新狀態：keep=max(x, keep+x)，drop=max(drop+x, oldKeep)。全負陣列不能以零初始化，因此從首元素建立狀態，並回傳所有狀態中的最大值。每個元素只做常數次運算，複雜度 O(n) 和 O(1)。 」
常見錯誤
- 只執行 Kadane 演算法，完全沒有表達刪除一次的狀態。
- 把
drop初始化為 0，導致空子陣列或刪除虛擬元素。 - 用更新後的
keep計算drop，把同一元素同時延長和刪除。 - 刪除後允許區間為空，卻沒有確認題目邊界。
- 只測試正數，遺漏全負、單元素和刪除端點。
錯誤表現與修正
陣列 [-5] 若回傳 0，表示實作違反非空約束；陣列 [1,-2,0,3] 若沒有優於普通 Kadane 的結果，表示刪除狀態沒有參與答案。修正時先寫狀態不變量，再用小陣列逐步列出轉移。
生產化實作
使用足夠寬的整數型別，避免總和超出輸入元素型別。若需要回傳區間而非只有總和，額外保存起點、刪除位置與終點元資料；狀態數量仍保持常數，但相等值時要規定穩定的取捨規則。
驗證清單
至少測試單元素、全負、全正、刪除中間負數、刪除端點、多個最佳解和最大數值。小規模輸入可用枚舉刪除位置加 Kadane 的 O(n²) 參考實作做隨機對拍，確認線性實作結果一致。
追問及應對
如果必須刪除一個元素怎麼辦？
答案不能直接取 keep，因為必須使用 drop 狀態；單元素陣列會變成無合法非空結果，題目需要額外定義回傳值或最小輸入長度。
能否用前綴和解決？
前綴和可以枚舉刪除位置和區間，通常需要 O(n²)；若再配合左右最大子陣列預處理，可達到 O(n) 但需要 O(n) 空間。兩個狀態的掃描方案更節省空間。
如何還原實際區間？
為每個狀態攜帶起點和刪除索引。發生重新開始時重置起點，發生刪除目前元素時記錄索引；最後從最大答案狀態回溯終點即可。
評分標準
- 狀態定義：清楚區分未刪除與已刪除一次。
- 轉移正確：使用舊狀態，覆蓋重新開始、延長與刪除目前元素。
- 邊界完整：處理全負、單元素、必須非空與整數溢出。
- 複雜度準確：達到 O(n) 時間與 O(1) 額外空間。
- 驗證充分：提出枚舉參考實作和涵蓋邊界的測試集合。
合規檢查
確認狀態轉移、非空邊界與複雜度結論在回答中保持一致。
面試作答要點
先寫兩個狀態與不變量，再給出兩條轉移；強調保存舊值、首元素初始化和答案同時檢查兩個狀態，最後說明複雜度與隨機對拍。
一句話總結
允許一次刪除只需在 Kadane 的連續區間狀態上增加「已刪除」維度，即可在線性時間、常數空間內求出非空最大和。