Kadane's Algorithm: Maximum Subarray Sum Explained

Kadane’s Algorithm finds the maximum sum of a contiguous subarray in O(n).

It is a dynamic programming pattern disguised as a greedy scan:

At every index decide: extend the previous subarray, or start fresh here?

Focus on recognizing:

“Maximum contiguous sum” → Kadane

Core Template

public int maxSubArray(int[] nums) {
    int currentSum = nums[0];
    int maxSum = nums[0];

    for (int i = 1; i < nums.length; i++) {
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        maxSum = Math.max(maxSum, currentSum);
    }

    return maxSum;
}

def max_sub_array(nums):
    current = nums[0]
    best = nums[0]

    for i in range(1, len(nums)):
        current = max(nums[i], current + nums[i])
        best = max(best, current)

    return best

int maxSubArray(vector<int>& nums) {
    int cur = nums[0];
    int best = nums[0];

    for (int i = 1; i < (int)nums.size(); i++) {
        cur = max(nums[i], cur + nums[i]);
        best = max(best, cur);
    }

    return best;
}

function maxSubArray(nums) {
  let cur = nums[0];
  let best = nums[0];

  for (let i = 1; i < nums.length; i++) {
    cur = Math.max(nums[i], cur + nums[i]);
    best = Math.max(best, cur);
  }

  return best;
}

Seeding with nums[0] (not 0) makes all-negative arrays work automatically.

Kadane = drop the running prefix the moment it hurts more than it helps.

Variant 1: Reset Form

Watch cur/best evolve over [-2,1,-3,4,-1,2,1,-5,4] — the restart at index 3 and the final answer 6. Press ▶ to animate.

Kadane's Algorithm

Maximum subarray sum — compare the classic extend-or-restart walk against tracking which subarray wins.

Walk through the array keeping a running sum that either extends the current subarray or restarts at the current element. On the input, the best subarray is [4, -1, 2, 1] = 6. The key insight: a negative running sum never helps a future subarray, so drop it and start fresh. Seed with nums[0] (not 0) so all-negative arrays work correctly. Track the best sum seen throughout. Runs in O(n) time, O(1) space.

ARRAY VISUALIZER

Steps –

-2

-3

-1

-5

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        cur = best = nums[0]
                      
                        2
                        for i in 1..n-1:
                      
                        3
                          cur = max(nums[i],      // restart here
                      
                        4
                                    cur + nums[i]) // extend the run
                      
                        5
                          best = max(best, cur)
                      
                        6
                        return best

Same logic, written greedily:

public int maxSubArray(int[] nums) {
    int sum = 0;
    int max = Integer.MIN_VALUE;

    for (int num : nums) {
        sum += num;
        max = Math.max(max, sum);

        if (sum < 0) {
            sum = 0;
        }
    }

    return max;
}

def max_sub_array(nums):
    total = 0
    best = float("-inf")

    for num in nums:
        total += num
        best = max(best, total)

        if total < 0:
            total = 0

    return best

int maxSubArray(vector<int>& nums) {
    int sum = 0;
    int best = INT_MIN;

    for (int num : nums) {
        sum += num;
        best = max(best, sum);

        if (sum < 0) sum = 0;
    }

    return best;
}

function maxSubArray(nums) {
  let sum = 0;
  let max = -Infinity;

  for (const num of nums) {
    sum += num;
    max = Math.max(max, sum);

    if (sum < 0) sum = 0;
  }

  return max;
}

Two equivalent forms: DP (max(num, cur + num)) and greedy (reset negatives). Pick one and stay consistent.

Variant 2: Minimum Subarray Sum

Flip min/max and Kadane hunts for the most negative stretch instead.

Minimum Subarray Sum

Find the contiguous subarray with the smallest sum.

Same Kadane skeleton as max, but with min: at each cell keep the smaller of a fresh start vs extending the current run, and track the running best with min. Identical logic with min/max flipped.

ARRAY VISUALIZER

Steps –

-4

-3

-1

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        cur = best = nums[0]
                      
                        2
                        for i in 1..n-1:
                      
                        3
                          cur = min(nums[i], cur + nums[i])
                      
                        4
                          best = min(best, cur)

Invert every comparison:

public int minSubArray(int[] nums) {
    int current = nums[0];
    int min = nums[0];

    for (int i = 1; i < nums.length; i++) {
        current = Math.min(nums[i], current + nums[i]);
        min = Math.min(min, current);
    }

    return min;
}

def min_sub_array(nums):
    current = nums[0]
    best = nums[0]

    for i in range(1, len(nums)):
        current = min(nums[i], current + nums[i])
        best = min(best, current)

    return best

int minSubArray(vector<int>& nums) {
    int cur = nums[0];
    int best = nums[0];

    for (int i = 1; i < (int)nums.size(); i++) {
        cur = min(nums[i], cur + nums[i]);
        best = min(best, cur);
    }

    return best;
}

function minSubArray(nums) {
  let cur = nums[0];
  let best = nums[0];

  for (let i = 1; i < nums.length; i++) {
    cur = Math.min(nums[i], cur + nums[i]);
    best = Math.min(best, cur);
  }

  return best;
}

Variant 3: Circular Array

total − worstSubarray = best wrap-around answer. Compare with straight Kadane.

Maximum Circular Subarray Sum

You are given an integer array arranged in a circle. Find the maximum sum of a non-empty subarray. Unlike a normal array, a subarray can wrap from the end of the array back to the beginning. For example, in [5, -3, 5], the subarray containing the last 5 and the first 5 is valid, giving a sum of 10.

There are two ways to form the maximum subarray: it can stay within the normal array boundaries, or it can wrap around the ends. First, use Kadane's algorithm to find the best normal subarray. For a wrapping subarray, think of removing one contiguous middle section from the array. To maximize what remains, remove the minimum-sum subarray. Therefore, the wrapping sum is total sum − minimum subarray sum. The answer is the larger of the normal Kadane result and this wrapping result. If every number is negative, the wrapping formula would produce 0, which represents an empty subarray, so we use the normal Kadane result instead.

ARRAY VISUALIZER

Steps –

-3

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        straight = kadaneMax(nums)
                      
                        2
                        total = sum(nums)
                      
                        3
                        wrap = total − kadaneMin(nums)
                      
                        4
                        answer = max(straight, wrap)   // if wrap > 0

The max circular subarray is either a normal Kadane result or total − minimumSubarray:

public int maxSubarraySumCircular(int[] nums) {
    int total = 0;
    int curMax = 0, maxSum = nums[0];
    int curMin = 0, minSum = nums[0];

    for (int num : nums) {
        total += num;

        curMax = Math.max(curMax + num, num);
        maxSum = Math.max(maxSum, curMax);

        curMin = Math.min(curMin + num, num);
        minSum = Math.min(minSum, curMin);
    }

    if (maxSum < 0) return maxSum;   // all negative

    return Math.max(maxSum, total - minSum);
}

def max_subarray_sum_circular(nums):
    total = nums[0]
    cur_max = max_sum = nums[0]
    cur_min = min_sum = nums[0]

    for num in nums[1:]:
        total += num

        cur_max = max(cur_max + num, num)
        max_sum = max(max_sum, cur_max)

        cur_min = min(cur_min + num, num)
        min_sum = min(min_sum, cur_min)

    if max_sum < 0:
        return max_sum

    return max(max_sum, total - min_sum)

int maxSubarraySumCircular(vector<int>& nums) {
    int total = 0;
    int curMax = 0, maxSum = nums[0];
    int curMin = 0, minSum = nums[0];

    for (int num : nums) {
        total += num;

        curMax = max(curMax + num, num);
        maxSum = max(maxSum, curMax);

        curMin = min(curMin + num, num);
        minSum = min(minSum, curMin);
    }

    if (maxSum < 0) return maxSum;

    return max(maxSum, total - minSum);
}

function maxSubarraySumCircular(nums) {
  let total = 0;
  let curMax = 0,
    maxSum = nums[0];
  let curMin = 0,
    minSum = nums[0];

  for (const num of nums) {
    total += num;

    curMax = Math.max(curMax + num, num);
    maxSum = Math.max(maxSum, curMax);

    curMin = Math.min(curMin + num, num);
    minSum = Math.min(minSum, curMin);
  }

  if (maxSum < 0) return maxSum;

  return Math.max(maxSum, total - minSum);
}

The maxSum < 0 guard handles all-negative arrays where total − minSum would be an empty wrap.

Common Mistakes

Initializing maxSum to 0.

Fails on all-negative arrays — seed with nums[0].

Confusing Kadane with sliding window.

Kadane is decision-based (extend or restart), not a fixed window.

Circular: forgetting the guard.

When everything is negative, wrapping would select zero elements — return the plain max instead.

Complexity

Variant	Time
All	O(n)
Space	O(1)

⚠️ Animation & Content Notice

Kadane's Algorithm

Core Template

Variant 1: Reset Form

⚠️ Animation & Content Notice

Kadane's Algorithm

Variant 2: Minimum Subarray Sum

⚠️ Animation & Content Notice

Minimum Subarray Sum

Variant 3: Circular Array

⚠️ Animation & Content Notice

Maximum Circular Subarray Sum

Common Mistakes

Complexity

Premium Content

My Private Notes

Earn Premium with Referrals

Core Template

Variant 1: Reset Form

Kadane's Algorithm

Variant 2: Minimum Subarray Sum

Minimum Subarray Sum

Variant 3: Circular Array

Maximum Circular Subarray Sum

Common Mistakes

Complexity

Premium Content

My Private Notes