DSA AnimatorDSA animations
Maximum Subarray LC #53 Medium Kadane's
Problem

Given an integer array nums, find the subarray with the largest sum, and return its sum.

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.
Constraints: 1 ≤ nums.length ≤ 10⁵  |  −10⁴ ≤ nums[i] ≤ 10⁴
Try Examples
Custom:
Approach
Kadane's Algorithm — Greedy Extend or Reset
Extend the current subarray by adding nums[i]. If currSum drops below 0, a negative prefix can't help — reset to 0 and start fresh. maxSum tracks the global best. O(n) time, O(1) space!
Array
nums[] — current window highlighted
currSum
0
maxSum
−∞
Variables
i
—
nums[i]
—
currSum
—
maxSum
—
Step Logic
Press ▶ Play or Next Step to begin.
🎉
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
currSum = 0, maxSum = −∞
2
currSum += nums[i]
3
maxSum = max(maxSum, currSum)
4
If currSum < 0: reset to 0
Time
O(n)
Space
O(1)
Why It Works

A negative prefix can never improve a future subarray — it only drags the sum down. When currSum < 0, reset to 0 (start fresh from next element). At each index, currSum equals the maximum subarray sum ending here. maxSum tracks the global best across all positions.

How to solve Maximum Subarray

LeetCode 53 · Medium · Arrays · Pattern: Kadane's Algorithm

Why the obvious approach is slow

Checking every subarray is O(n²). And you cannot simply skip negatives, because the best run here contains a −1.

The key idea

At each index, either extend the current run, or start a fresh run from here. If the running sum has gone negative, it only hurts what comes next, so drop it.

Remember

Remember Kadane's rule: extend the run, or restart when the run is negative. Keep the best sum separately from the current run.

Run the animation above on your own input, or watch the 1:16 video explanation of Maximum Subarray with a dry run and Java code.

More Arrays problems