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 Sam K., 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
More DP 1D practice problems
- 45. Jump Game II
- 55. Jump Game
- 123. Best Time to Buy and Sell Stock III
- 134. Gas Station
- 188. Best Time to Buy and Sell Stock IV
- 213. House Robber II
- 256. Paint House
- 265. Paint House II