最后活跃于 5 days ago

Interview prep notes

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.*
上一页 下一页