# 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. ```python def max_subarray(nums): best = cur = nums[0] for x in nums[1:]: cur = max(x, cur + x) best = max(best, cur) return best ``` Initialising with `nums[0]` (not 0) correctly handles arrays that are all negative, a case interviewers like to test. ## Variations - **Return the indices:** remember where `cur` was last reset; update `start`/`end` whenever `best` improves. - **Maximum Product Subarray (152):** track both the max and the min product, because a negative number flips them. - **Circular array (918):** answer = max(normal Kadane, total sum minus the *minimum* subarray), unless every number is negative. - **Best Time to Buy and Sell Stock (121):** Kadane on the daily price differences. ## Explaining it as DP Say: "`dp[i]` is the best sum of a subarray ending at `i`; `dp[i] = max(nums[i], dp[i-1] + nums[i])`, and I only need the previous value, so I keep one variable." Framing it this way shows you understand *why* it works, not just the trick. --- *Disclosure: I'm part of the [Linkjob AI](https://www.linkjob.ai/) team (an AI interview assistant). Free to share.*