linkjobai / Kadane's Algorithm: Maximum Subarray in One Pass
0 gustos
0 bifurcaciones
1 archivos
Última actividad 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):
Siguiente
Anterior