Greedy — Maximum Subarray (Kadane)
↗ LeetCode: Maximum Subarray · Medium · pattern chapter →
Asked atMetaAmazonGoogleMicrosoftLinkedInBloombergApple
Max sum of a contiguous non-empty subarray.
Example 1 — nums=[-2,1,-3,4,-1,2,1,-5,4] → 6 ([4,-1,2,1]) Example 2 — nums=[1] → 1Example 3 — nums=[5,4,-1,7,8] → 23
Constraints — 1 ≤ n ≤ 10⁵; -10⁴ ≤ nums[i] ≤ 10⁴. Brute enumerates every subarray — O(n²) = 10¹⁰ ops at n=10⁵ (TLE). Kadane's DP is O(n) = 10⁵ ops; divide & conquer variant is O(n log n) = 1.7·10⁶ ops.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
⏱️Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — All subarrays
O(n²). Baseline.
Approach 2 — Kadane (canonical)
Insight. curr = max(x, curr + x) — either extend or restart. Global answer = max over all i.
java
int maxSubArray(int[] nums) {
int cur = nums[0], best = nums[0];
for (int i = 1; i < nums.length; i++) {
cur = Math.max(nums[i], cur + nums[i]);
best = Math.max(best, cur);
}
return best;
}1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
Execution Trace
Step 1 / 3restart
Complexity — Time O(n); Space O(1).
Approach 3 — Divide & Conquer
max(left, right, crossing). O(n log n). Interview curiosity.
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| All subarrays | O(n²) | O(1) | baseline |
| Kadane | O(n) | O(1) | canonical |
| D&C | O(n log n) | O(log n) | trivia |
When to use which
- Standard → Kadane.
- "Return the subarray" → track
(bestStart, bestEnd)alongside sums. - Circular array → Maximum Sum Circular Subarray — Kadane + reverse.
✨AI Study CompanionBeta
Related problems
- Maximum Product Subarray — min/max dual tracking
- Maximum Sum Circular Subarray
- Best Time to Buy and Sell Stock
Was this page helpful?
📚 Related problems