← Back to DSA Animator
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.