ToolMight LogoToolMight
MediumDynamic ProgrammingSliding WindowPattern: Kadane's AlgorithmPattern: Running Sum

Maximum Subarray (Kadane's Algorithm)

Find the contiguous slice of an array that yields the largest sum. Kadane's algorithm demonstrates the art of shedding negative historical baggage in O(n) linear time.

Problem Statement

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

A subarray is a contiguous non-empty sequence of elements within an array.

Examples & Constraints

Example 1
Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Explanation: The contiguous subarray [4, -1, 2, 1] has the largest sum = 6.
Example 2
Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum = 1.
Constraints
  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

Kadane's Algorithm (Dynamic Reset)

Optimal Approach
Time:O(n)
Space:O(1)

Maintain a running current sum. At each element, decide whether to append to the existing sum or start a fresh subarray if the accumulated sum drops below zero.

Time ComplexityO(n)

Single linear pass over the N elements of the array.

Space ComplexityO(1)

Only two accumulator variables (currentSum, maxSum) are stored.

Underlying algorithmic logic

The Core Mental Model: Discarding Toxic Debt

Imagine you are walking along an array accumulating wealth. Positive numbers earn you money, and negative numbers represent debts.

If at any point your accumulated total becomes negative (currentSum < 0), that prefix is toxic baggage.
Adding a negative balance to whatever number comes next will strictly drag down that next number's potential.

So the rule is simple: the second your current total dips below 0, cut your losses, reset to 0, and start a fresh subarray.

The All-Negative Trap (Crucial Interview Detail)

A common junior mistake is initializing maxSum = 0.
What happens if the input is nums = [-5, -2, -8]?
Because the problem demands a non-empty subarray, returning 0 is wrong—the correct answer is -2.

By initializing maxSum = nums[0] and calculating:

currentSum += num
maxSum = max(maxSum, currentSum)
if currentSum < 0: currentSum = 0

We record the least-negative element (-2) before resetting currentSum, naturally handling all-negative arrays without any awkward branch conditions!

Step-by-step execution walkthrough

1
Element -2

currentSum = -2. maxSum = -2. Reset currentSum = 0 (since < 0).

currentSum = 0, maxSum = -2
2
Element 1

currentSum = 1. maxSum = max(-2, 1) = 1.

currentSum = 1, maxSum = 1
3
Subarray [4, -1, 2, 1]

Progresses: 4 -> 3 -> 5 -> 6. maxSum reaches peak 6.

currentSum = 6, maxSum = 6
Advantages
  • •Optimal O(n) runtime
  • •Constant O(1) space
  • •Handles all-negative arrays cleanly when initialized to nums[0]
Trade-offs
  • •Does not naturally yield the start/end indices without extra index tracking variables

Code Implementations

Copy & paste production-ready solutions for Kadane's Algorithm (Dynamic Reset) in your language of choice

File: solution.py
Python
def max_sub_array(nums: list[int]) -> int:
    max_sum = nums[0]
    current_sum = 0
    for num in nums:
        current_sum += num
        max_sum = max(max_sum, current_sum)
        if current_sum < 0:
            current_sum = 0
    return max_sum
if __name__ == "__main__":
    nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    print(f"Maximum Subarray Sum: {max_sub_array(nums)}")
Interactive visualizer available

Understand Sliding Window Visually

Track contiguous subarrays of a larger array using start/end boundary pointers to avoid redundant recalculations. Test live edge cases and watch memory state transitions step-by-step.

Launch Sliding Window Visualizer

Frequently Asked Questions

Related Logic & Algorithm Problems

All problems
EasySliding Window
Visualizer

Best Time to Buy and Sell Stock

Determine the maximum single-transaction profit from daily stock prices. A classic demonstration of how tracking a running minimum transforms an O(n²) pair search into an O(n) single pass.

1 approach(O(n))
Learn logic
EasyArrays & Hashing
Visualizer

Two Sum

Find the two numbers in an array that sum up to a target value. The quintessential problem for learning how to trade memory for speed using a Hash Map.

2 approaches(O(n))
Learn logic
EasyDynamic Programming
Visualizer

Climbing Stairs

Count the distinct ways to reach the top of an n-step staircase when hopping 1 or 2 steps at a time. The premier gentle introduction to Dynamic Programming and state transition.

1 approach(O(n))
Learn logic