linkjobai 修订了这个 Gist 5 days ago. 转到此修订
1 file changed, 32 insertions
kadane.md(文件已创建)
| @@ -0,0 +1,32 @@ | |||
| 1 | + | # Kadane's Algorithm: Maximum Subarray in One Pass | |
| 2 | + | ||
| 3 | + | **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. | |
| 4 | + | ||
| 5 | + | ## The insight | |
| 6 | + | ||
| 7 | + | 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. | |
| 8 | + | ||
| 9 | + | ```python | |
| 10 | + | def max_subarray(nums): | |
| 11 | + | best = cur = nums[0] | |
| 12 | + | for x in nums[1:]: | |
| 13 | + | cur = max(x, cur + x) | |
| 14 | + | best = max(best, cur) | |
| 15 | + | return best | |
| 16 | + | ``` | |
| 17 | + | ||
| 18 | + | Initialising with `nums[0]` (not 0) correctly handles arrays that are all negative, a case interviewers like to test. | |
| 19 | + | ||
| 20 | + | ## Variations | |
| 21 | + | ||
| 22 | + | - **Return the indices:** remember where `cur` was last reset; update `start`/`end` whenever `best` improves. | |
| 23 | + | - **Maximum Product Subarray (152):** track both the max and the min product, because a negative number flips them. | |
| 24 | + | - **Circular array (918):** answer = max(normal Kadane, total sum minus the *minimum* subarray), unless every number is negative. | |
| 25 | + | - **Best Time to Buy and Sell Stock (121):** Kadane on the daily price differences. | |
| 26 | + | ||
| 27 | + | ## Explaining it as DP | |
| 28 | + | ||
| 29 | + | 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. | |
| 30 | + | ||
| 31 | + | --- | |
| 32 | + | *Disclosure: I'm part of the [Linkjob AI](https://www.linkjob.ai/) team (an AI interview assistant). Free to share.* | |
上一页
下一页