linkjobai / Kadane's Algorithm: Maximum Subarray in One Pass
0 喜歡
0 分支
1 檔案
最後活躍 5 days ago
Interview prep notes
Kadane's Algorithm: Maximum Subarray in One Pass
Maximum Subarray (LeetCode 53) asks for the largest sum of any contiguous subarray. Brute force checks every pair of endpoints, which is O(n²). Kadane's algorithm does it in O(n) with O(1) memory.
The insight
At each index, the best subarray ending here either extends the previous best one or starts fresh. You start fresh whenever the running sum has gone negative, because a negative prefix can only make things worse.
def max_subarray(nums):
上一頁
下一頁