Developers

Maximum Subarray

MediumDynamic programmingGrade AAlso known as LeetCode 53

You get a list of integers. A subarray is a run of numbers that sit next to each other in the list, and it must contain at least one number.

Return the largest sum that any subarray can have.

Examples

Input nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output 6
The run 4, -1, 2, 1.
Input nums = [1]
Output 1
Input nums = [-3, -1, -2]
Output -1
All numbers are negative, so the best run is the single largest number.

Constraints

  • 1 <= nums.length <= 100,000
  • -10,000 <= nums[i] <= 10,000

Stuck? Take one hint at a time

Common mistakes
  • Starting the best at 0, which gives a wrong answer when every number is negative.
  • Resetting the run to 0 instead of to the current number.
  • Using extend-only logic and never starting fresh.
  • Forgetting to update the best after the run changes.
Questions an interviewer may ask next
  • Also return the start and end positions of the best run.
  • The list is circular, so a run may wrap around the end. (Total minus the minimum subarray.)
  • Find the maximum product subarray instead. What makes it harder?
  • Solve it with divide and conquer and compare the cost.

How often this is reported

Commonly reported across 14 of 25 tracked companies
14/25

Grade A: Reported in several independent candidate sources. This reflects what candidates report, not a guarantee of what any company will ask.