Algorithm

Maximum Subarray (Kadane's)

Arrays & Strings Pattern

Maximum Subarray (Kadane's)

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

CONSTRAINTS
  • 1 <= nums.length <= 10⁵
  • -10⁴ <= nums[i] <= 10⁴
EXAMPLE 1
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
The best slice is [4, -1, 2, 1] with sum 6. Note it keeps the -1 inside: its neighbors more than repay the loss, and any slice avoiding it does worse.
EXAMPLE 2
Input: nums = [1]
Output: 1
Only one non-empty subarray exists — the single element itself.
EXAMPLE 3
Input: nums = [5,4,-1,7,8]
Output: 23
The whole array wins: even the -1 is worth keeping for the 7 and 8 behind it.
EXAMPLE 4
Input: nums = [-3,-5,-1]
Output: -1
All negative. An empty subarray is not allowed, so the answer is the least negative single element, -1 — not 0.
Does 'subarray' mean the elements must be contiguous?
Yes — an unbroken slice of the array, in its original order. Picking non-adjacent elements would be a subsequence, which is a different problem. Always confirm this word with the interviewer.
If all numbers are negative, do I return 0 for an empty subarray?
No. The subarray must contain at least one number, so with all negatives the answer is the single least-negative element.
Do I need to return the actual subarray, or just the sum?
Just the sum. (The scan can be extended to also record start and end indices if a follow-up asks for the slice itself.)

Finding the maximum subarray sum means identifying a contiguous chunk of numbers within an array that adds up to the highest possible total. The challenge is that negative numbers can "reset" our progress, making it difficult to decide where a subarray should start and end.

Quadratic Windows (O(N²))

The most direct way to solve this is to check every possible subarray. We pick a starting index, then scan to the right to calculate every possible ending index, keeping track of the best sum we find.

python
max_sum = nums[0]
for i in range(len(nums)):
    current_sum = 0
    for j in range(i, len(nums)):
        current_sum += nums[j]
        max_sum = max(max_sum, current_sum)
return max_sum
Dumping Negative Debt

The brute force is slow because it recalculates every window from scratch. The core insight is that a negative sum is dead weight. If our current total is negative, adding it to the next number will only make that number smaller. We are always better off dumping the negative debt and starting fresh.

Kadane's Algorithm (O(N))

Instead of checking every window, we walk through the array once. At every step, we decide: "Should I continue the current streak, or should I start a brand new streak at this number?" If the previous streak is negative, it's "debt" — we are always better off resetting the count to the current number.

python
current_streak = 0
max_result = nums[0]
for x in nums:
    # If the current streak is negative, it helps no one. Start fresh at x.
    current_streak = max(x, current_streak + x)
    max_result = max(max_result, current_streak)
return max_result
Worked Example:[-2, 1, -3, 4, -1]
0
-2
x
1
1
2
-3
3
4
4
-1
We begin with the first element, -2. We initialize our running subarray streak to -2, and the maximum sum found so far to -2.
0
-2
1
1
x
2
-3
3
4
4
-1
We inspect the number 1. Since our previous subarray streak was negative (-2), it would only drag down our sum. We discard it, start a fresh subarray at 1, and update our maximum sum to 1.
0
-2
1
1
2
-3
x
3
4
4
-1
We inspect the number -3. We add it to our current streak of 1, bringing the running sum to -2. Our maximum sum remains 1.
0
-2
1
1
2
-3
3
4
x
4
-1
We inspect the number 4. Since the previous streak was negative (-2), we dump it and start a new subarray here. Our running streak becomes 4, which is our new maximum sum.
0
-2
1
1
2
-3
3
4
4
-1
x
We inspect the number -1. Adding it to our current streak of 4 brings the running sum to 3. The maximum sum remains 4, which is our final answer.
Interactive Strategy Visualization

The Streak Decision

Strategy: Kadane's Choice
Max Found: -2
-2
1
-3
4
-1
2
1
-5
4
Current Bag
-2
Starting with -2. Since it's negative, it immediately drags our streak down.
O(N²) Brute Force
→
O(N) Kadane's