Skip to main content

53. Maximum Subarray

medium

Find 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 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

Input
nums = [-2,1,-3,4,-1,2,1,-5,4]
Output
6

Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Example 2

Input
nums = [1]
Output
1

Example 3

Input
nums = [5,4,-1,7,8]
Output
23

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

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
  • Google
  • Bloomberg
  • LinkedIn

Practice these live with InterviewChamp.AI

Drill Maximum Subarray and Arrays problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →