53. Maximum Subarray
mediumFind the contiguous subarray with the largest sum. The classic Kadane's algorithm problem — one pass, constant space, foundational to dynamic-programming-on-arrays intuition.
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]1Example 3
nums = [5,4,-1,7,8]23Solve 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 tries every subarray — O(n^2) or O(n^3). Too slow.
Hint 2
Ask: at every position i, what is the maximum-sum subarray that ENDS at i?
Hint 3
Kadane's: at index i, either extend the previous best-ending-here by adding nums[i], or start fresh at nums[i]. currMax = max(nums[i], currMax + nums[i]); globalMax = max(globalMax, currMax).
Solution approach
Reveal approach
Kadane's algorithm. Track two values: currMax (best sum of a subarray ending at the current index) and globalMax (best sum found anywhere). For each element, currMax becomes max(nums[i], currMax + nums[i]) — you either start a new subarray at nums[i] or extend the running one. Update globalMax with the new currMax. Return globalMax at the end. Handles all-negative arrays naturally since you take max(nums[i], ...) and never force an empty subarray.
Complexity
- Time
- O(n)
- Space
- O(1)
Related patterns
- dynamic-programming
- kadane
Related problems
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
- Microsoft
- Bloomberg
More Arrays practice problems
- 1. Two Sum
- 11. Container With Most Water
- 15. 3Sum
- 26. Remove Duplicates from Sorted Array
- 31. Next Permutation
- 41. First Missing Positive
- 48. Rotate Image
- 54. Spiral Matrix