mafeshsho8lmafeshsho8l
Get Started
All coding questions

Maximum Subarray

medium
Blind 75NeetCode 150dynamic-programminggreedyarrays

Problem

Given a list of integers, find the contiguous subarray with the largest sum and return that sum. The subarray must contain at least one element.

Examples

Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
The subarray [4, -1, 2, 1] sums to 6.
Input: nums = [-1]
Output: -1
The single element is the best available.

Constraints

  • • 1 <= nums.length <= 10^5
  • • -10^4 <= nums[i] <= 10^4
Hints(tap to reveal)
  • 1. Decide at each element whether to extend or restart.
  • 2. This is Kadane's algorithm.
Optimal approach(spoiler)
  1. Track the best subarray sum ending at the current position.
  2. At each element, either extend the previous run or start fresh at this element.
  3. Update a global maximum with the running best.
  4. Return the global maximum.
  5. O(n) time, O(1) space.

Ready to solve it?

Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.

Practice in the editor