Finding the Maximum Subarray Sum in Linear Time with Kadanes Algorithm

The Maximum Subarray Problem is a foundational algorithmic challenge: given a sequence of integers containing both positive and negative values, find the contiguous subarray that produces the largest aggregate sum. A brute-force approach that checks every conceivable starting and ending boundary requires computing nested loops over quadratic or cubic time complexity, quickly becoming unviable as dataset sizes scale into thousands of elements. In 1984, Joseph Kadane designed an elegant dynamic programming algorithm that solves the problem in a single pass with linear time and $O(1)$ auxiliary memory.

Kadane's algorithm operates on a simple yet profound insight: at each position in the array, the maximum contiguous sum ending at that index is either the current element alone or the current element added to the previous maximum contiguous sum. By deciding whether to extend an existing subarray or discard it to start fresh, the algorithm eliminates redundant recalculations. Handling boundary conditions correctly—such as entirely negative integer arrays or empty input collections—ensures robustness across real-world data processing, financial analytics, and signal processing workflows.

Example #

// Basic Kadane's algorithm computing the maximum contiguous sum
function maxSubarraySum(nums) {
  if (nums.length === 0) return 0;
  
  let currentSum = nums[0];
  let maxSum = nums[0];

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

  return maxSum;
}

Implementation #

/**
 * Computes the maximum subarray sum and extracts subarray slice indices.
 * Runs in O(N) linear time with O(1) auxiliary space complexity.
 *
 * @param {number[]} nums - Array of positive and negative integers.
 * @returns {Object} Result object containing maxSum, startIndex, endIndex, and subarray.
 */
function findMaximumSubarray(nums) {
  // Guard clause for empty array input
  if (!Array.isArray(nums) || nums.length === 0) {
    return { maxSum: 0, startIndex: -1, endIndex: -1, subarray: [] };
  }

  let currentSum = nums[0];
  let maxSum = nums[0];

  let startIndex = 0;
  let endIndex = 0;
  let tempStartIndex = 0;

  for (let i = 1; i < nums.length; i++) {
    const value = nums[i];

    // If adding the current value to currentSum is worse than the value alone,
    // start a new contiguous subarray from the current index.
    if (value > currentSum + value) {
      currentSum = value;
      tempStartIndex = i;
    } else {
      currentSum += value;
    }

    // Update global maximum and commit the true boundary indices
    if (currentSum > maxSum) {
      maxSum = currentSum;
      startIndex = tempStartIndex;
      endIndex = i;
    }
  }

  return {
    maxSum,
    startIndex,
    endIndex,
    subarray: nums.slice(startIndex, endIndex + 1)
  };
}

// Edge case 1: Mixed positive and negative integers
const sample = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
console.log(findMaximumSubarray(sample));
// Output: { maxSum: 6, startIndex: 3, endIndex: 6, subarray: [4, -1, 2, 1] }

// Edge case 2: Array containing only negative integers
const allNegative = [-8, -3, -6, -2, -5];
console.log(findMaximumSubarray(allNegative));
// Output: { maxSum: -2, startIndex: 3, endIndex: 3, subarray: [-2] }

Main Point: Kadane's algorithm evaluates contiguous subarrays in linear time by greedily deciding at each index whether to extend the accumulated sum or begin a new subarray sequence.

Credits #

Photo by Pawel Czerwinski on Unsplash

← Home