MediumHigh Frequency20 min
Kadane's Algorithm
Find the maximum subarray sum in O(n) using the local vs global maximum pattern.
Kadane's algorithm finds the maximum sum subarray in O(n) by deciding at each index: extend current subarray or start fresh.
Kadane's Algorithm
Operations — Step by Step
Kadane's — Max Subarray
O(n)cur resets to nums[i] when extending would make it worseStep-by-step1 / 7
i=0: cur=-2, best=-2
Initialize cur = nums[0] = -2. best = -2.