Kadane's Algo

Medium

Problem

Given an integer array (it may contain negative numbers), find the contiguous subarray with the largest sum and return that sum. The subarray must contain at least one element.

Example 1

Input:  [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6

The subarray [4, -1, 2, 1] has sum 6.

Example 2

Input:  [-3, -1, -2]
Output: -1

All negative: the best is the single largest element.

Also asked as: find Largest sum contiguous Subarray · largest sum contiguous subarray

Test cases

Case 1

Input:    [-2,1,-3,4,-1,2,1,-5,4]
Expected: 6

Case 2

Input:    [1]
Expected: 1

Case 3

Input:    [5,4,-1,7,8]
Expected: 23

Case 4

Input:    [-3,-1,-2]
Expected: -1

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution3 approaches

1. Kadane (running sum)

Time O(n)Space O(1)

At each index keep the best subarray sum ending here: either extend the previous one or start fresh.

function maxSubArray(nums) {
let best = nums[0], cur = 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;
}

To also return the indices, record start when cur resets and end when best updates.

2. Prefix sum + running minimum

Time O(n)Space O(1)

max subarray ending at i = prefix[i] − min(prefix[0..i−1]). Same complexity, useful when you already have prefix sums.

function maxSubArray(nums) {
let prefix = 0, minPrefix = 0, best = -Infinity;
for (const x of nums) {
prefix += x;
best = Math.max(best, prefix - minPrefix);
minPrefix = Math.min(minPrefix, prefix);
}
return best;
}

3. Divide and conquer

Time O(n log n)Space O(log n)

Best subarray is entirely left, entirely right, or crosses the midpoint. Asked to test recursion/merge thinking.

function maxSubArray(nums, lo = 0, hi = nums.length - 1) {
if (lo === hi) return nums[lo];
const mid = (lo + hi) >> 1;
let leftBest = -Infinity, sum = 0;
for (let i = mid; i >= lo; i--) { sum += nums[i]; leftBest = Math.max(leftBest, sum); }
let rightBest = -Infinity; sum = 0;
for (let i = mid + 1; i <= hi; i++) { sum += nums[i]; rightBest = Math.max(rightBest, sum); }
return Math.max(
maxSubArray(nums, lo, mid),
maxSubArray(nums, mid + 1, hi),
leftBest + rightBest,
);
}