53. Maximum Subarray
mediumFind the contiguous subarray with the largest sum. Kadane's algorithm in five lines — the canonical 1D DP every interviewer expects you to know cold.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Problem
Given an integer array nums, find the subarray with the largest sum, and return its sum.
Constraints
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4
Examples
Example 1
nums = [-2,1,-3,4,-1,2,1,-5,4]6Explanation: The subarray [4,-1,2,1] has the largest sum 6.
Example 2
nums = [1]1Explanation: The subarray [1] has the largest sum 1.
Example 3
nums = [5,4,-1,7,8]23Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
Brute force O(n^2) is to try every (i, j) pair. Can you decide what to do at index i with only O(1) extra state?
Hint 2
Maintain current_sum = best sum ending exactly at i. Either extend it with nums[i] or restart at nums[i].
Hint 3
Track best_overall = max(best_overall, current_sum) as you sweep.
Solution approach
Reveal approach
Kadane's algorithm. Maintain current = the maximum subarray sum that ENDS at the current index, and best = the overall maximum seen so far. For each num: current = max(num, current + num) (either restart at num or extend the prior subarray with num); best = max(best, current). Return best. The choice at each index is binary — restart or extend — because any optimal subarray ending at i either includes the optimal one ending at i-1 or starts fresh at i. O(n) time, O(1) space. Handles all-negative arrays correctly because best is initialized to nums[0].
Complexity
- Time
- O(n)
- Space
- O(1)
Related patterns
- dynamic-programming
- kadane
- divide-and-conquer
Related problems
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
- Microsoft
- Apple
- Bloomberg
Practice these live with InterviewChamp.AI
Drill Maximum Subarray and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →