#53 Maximum Subarray
frequently reported atInfosysLinkedInMicrosoftTCSNVIDIAAmazon
the problem
In plain words
Find the contiguous subarray (at least one element) with the largest sum and return that sum.
in nums = [-2,1,-3,4,-1,2,1,-5,4]
out 6
[4,-1,2,1] sums to 6.
in nums = [1]
out 1
in nums = [5,4,-1,7,8]
out 23
- 1 ≤ n ≤ 10⁵
- -10⁴ ≤ nums[i] ≤ 10⁴
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternKadane / running bestDivide and conquer
The best subarray ending at i either extends the best one ending at i−1, or starts fresh at i. Start fresh exactly when the running sum has gone negative.
solutions
From brute force to optimal
Fix a start, extend the end one step at a time while keeping a running sum.
- For each start: sum = 0.
- For each end ≥ start: sum += nums[end]; update best.
n starts × up to n ends (re-summing each subarray would be O(n³)).
A sum and a best.
class Solution { public int maxSubArray(int[] nums) { int best = Integer.MIN_VALUE; for (int start = 0; start < nums.length; start++) { int sum = 0; for (int end = start; end < nums.length; end++) { sum += nums[end]; // extend instead of re-summing: O(n^2), not O(n^3) best = Math.max(best, sum); } } return best; }}The best subarray is in the left half, the right half, or crosses the middle.
- Recurse on both halves.
- Best crossing sum = best suffix of the left half + best prefix of the right half.
- Return the max of the three.
T(n) = 2T(n/2) + O(n) for the crossing scan.
Recursion depth of a balanced split.
class Solution { public int maxSubArray(int[] nums) { return solve(nums, 0, nums.length - 1); } private int solve(int[] a, int lo, int hi) { if (lo == hi) return a[lo]; int mid = lo + (hi - lo) / 2; int leftBest = solve(a, lo, mid), rightBest = solve(a, mid + 1, hi); int sum = 0, crossLeft = Integer.MIN_VALUE; // best sum ending exactly at mid for (int i = mid; i >= lo; i--) { sum += a[i]; crossLeft = Math.max(crossLeft, sum); } sum = 0; int crossRight = Integer.MIN_VALUE; // best sum starting exactly at mid + 1 for (int i = mid + 1; i <= hi; i++) { sum += a[i]; crossRight = Math.max(crossRight, sum); } return Math.max(Math.max(leftBest, rightBest), crossLeft + crossRight); }}current = max(nums[i], current + nums[i]); best = max(best, current).
- current = best = nums[0].
- For i ≥ 1: extend or restart.
- Track the best current ever seen.
One pass, O(1) work per element.
Two variables.
class Solution { public int maxSubArray(int[] nums) { int current = nums[0], best = nums[0]; for (int i = 1; i < nums.length; i++) { current = Math.max(nums[i], current + nums[i]); // extend, or start fresh here best = Math.max(best, current); } return best; }}Dry run
in the room
How to say it in the interview
talk track
- Clarify: at least one element must be chosen, so an all-negative array returns its largest element.
- Explain the choice at each index — extend or restart — then code it in four lines.
- If asked to return the subarray itself, track the start index when you restart and the end when best improves.
traps
- Starting with best = 0: wrong for all-negative input like [-3,-1,-2] (answer −1).
- Confusing subarray (contiguous) with subsequence (any elements).
what they ask next
Follow-ups
Maximum Product Subarray (LC 152)?
Track both the max and the min product ending at i — a negative number swaps them.
Circular array (LC 918)?
Answer = max(normal Kadane, total − minimum subarray), unless every number is negative. Solved in full later in this chapter.
before you submit
Edge cases to test
- All negative ([-3,-1,-2] → −1): never start best at 0.
- One element → that element.
- Zeros between negatives ([0,-1,0] → 0).
practise next
Similar problems
- #918Maximum Sum Circular SubarrayMediumin Arrays & Strings
- #152Maximum Product SubarrayMediumin Dynamic Programming
- #121Best Time to Buy and Sell StockEasyin Arrays & Strings