今天解的題目是第五十三題 Maximum Subarray，題目要求在一個整數陣列中找到連續子陣列的最大總和並回傳結果。舉例來說，若輸入陣列是 [-2,1,-3,4,-1,2,1,-5,4]，那麼答案是子陣列 [4,-1,2,1]，總和為 6。解題的核心思路是利用一個變數 curr_sum 來追蹤當前子陣列的和，並用另一個變數 max_sum 來保存迄今為止出現過的最大總和。在遍歷整個陣列的過程中，每一步都將當前元素加入 curr_sum，並檢查是否需要更新 max_sum。若此時 curr_sum 小於 0，就代表繼續攜帶這段總和只會拖累後續的結果，因此果斷將 curr_sum 重置為 0，從下一個元素重新開始累計。這樣的策略確保我們始終維持最佳的可能性，而不會被負數總和拖累。最終，當遍歷結束時，max_sum 就是整個陣列中最大子陣列的總和。
iThome鐵人賽
看影片追技術