Skip to content
LEETFLIX

Maximum Subarray

MediumArrayD&CDP
Solve on LeetCode

Kadane's algorithm: the whole DP fits in one line and one very good question.

01

Problem

Read the prompt, flip through the examples, then steal the idea.

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

Follow-up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Examples

Input

nums =
[-2, 1, -3, 4, -1, 2, 1, -5, 4]

Output

6

nums

-2
0
1
1
-3
2
4
3
-1
4
2
5
1
6
-5
7
4
8

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

02

Solution

2 approaches · Python and Go. Pick a tab — the walkthrough follows.

Optimal▶ Animated

cur = best subarray ending here; best = max over all cur.

At each element, either extend the current run or restart from this element, whichever is larger. Track the maximum cur ever seen.

Algorithm

  1. cur = best = nums[0].
  2. For each subsequent x: cur = max(x, cur + x).
  3. best = max(best, cur).
  4. Return best.
Time
O(n)
Space
O(1)
Solution.py
class Solution:    def maxSubArray(self, nums: list[int]) -> int:        best = cur = nums[0]        for x in nums[1:]:            cur = max(x, cur + x)   # extend the run, or restart here            best = max(best, cur)        return best
Watch this run

03

Interactive walkthrough

Playing “Kadane's algorithm”. Edit the input, hit Run, then scrub.

Approach: Kadane's algorithm

Loading animation…

Up next

#121Best Time to Buy and Sell Stock

Easy

Python · Go · Animated

#70Climbing Stairs

Easy

Python · Go · Animated