Kadane's Algorithm

Overview

Kadane's Algorithm is a dynamic programming technique that finds the maximum sum subarray in O(n) time and O(1) space. Named after Jay Kadane, it's one of the most elegant solutions to the "maximum subarray problem."

The key insight: at each position, decide whether to extend the previous subarray or start a new one. If the current element alone is better than extending the previous sum, start fresh. Otherwise, extend.

Kadane's algorithm is particularly useful for:

• Maximum sum subarray
• Maximum product subarray
• Maximum sum circular subarray
• Best time to buy and sell stock
• Maximum alternating sum

Pattern 1: Maximum Sum Subarray (Classic Kadane)

Find maximum sum of contiguous subarray.

function maxSubArray(nums: number[]): number {
  let maxSum = nums[0];
  let currentSum = nums[0];
  
  for (let i = 1; i < nums.length; i++) {
    // Either extend previous subarray or start new one
    currentSum = Math.max(nums[i], currentSum + nums[i]);
    maxSum = Math.max(maxSum, currentSum);
  }
  
  return maxSum;
}

Time: O(n), Space: O(1)

Explanation: currentSum represents maximum sum ending at current index. At each step, we choose: start fresh with nums[i] or extend previous currentSum.

With indices (to track subarray):

function maxSubArrayWithIndices(nums: number[]): [number, number, number] {
  let maxSum = nums[0];
  let currentSum = nums[0];
  let start = 0, end = 0, tempStart = 0;
  
  for (let i = 1; i < nums.length; i++) {
    if (currentSum < 0) {
      currentSum = nums[i];
      tempStart = i;
    } else {
      currentSum += nums[i];
    }
    
    if (currentSum > maxSum) {
      maxSum = currentSum;
      start = tempStart;
      end = i;
    }
  }
  
  return [maxSum, start, end];
}

Pattern 2: Maximum Product Subarray

Find maximum product of contiguous subarray (handles negatives).

function maxProduct(nums: number[]): number {
  let maxProd = nums[0];
  let minProd = nums[0];
  let result = nums[0];
  
  for (let i = 1; i < nums.length; i++) {
    // Swap if current is negative (min becomes max, max becomes min)
    if (nums[i] < 0) {
      [maxProd, minProd] = [minProd, maxProd];
    }
    
    maxProd = Math.max(nums[i], maxProd * nums[i]);
    minProd = Math.min(nums[i], minProd * nums[i]);
    
    result = Math.max(result, maxProd);
  }
  
  return result;
}

Time: O(n), Space: O(1)

Key insight: Negative numbers flip min/max. Track both because negative * min = large positive.

Pattern 3: Maximum Sum Circular Subarray

Find maximum sum subarray in circular array.

function maxSubarraySumCircular(nums: number[]): number {
  // Case 1: Maximum subarray in linear array (normal Kadane)
  let maxSum = nums[0];
  let currentMax = nums[0];
  
  // Case 2: Maximum sum wraps around (total - minimum subarray)
  let minSum = nums[0];
  let currentMin = nums[0];
  let totalSum = nums[0];
  
  for (let i = 1; i < nums.length; i++) {
    totalSum += nums[i];
    
    // Maximum subarray
    currentMax = Math.max(nums[i], currentMax + nums[i]);
    maxSum = Math.max(maxSum, currentMax);
    
    // Minimum subarray
    currentMin = Math.min(nums[i], currentMin + nums[i]);
    minSum = Math.min(minSum, currentMin);
  }
  
  // If all negative, return maxSum
  if (maxSum < 0) return maxSum;
  
  // Maximum is either normal max or (total - min)
  return Math.max(maxSum, totalSum - minSum);
}

Time: O(n), Space: O(1)

Explanation: Circular max is either normal max subarray OR wraps around (total sum - minimum subarray).

Pattern 4: Best Time to Buy and Sell Stock

Find maximum profit from one transaction (Kadane on differences).

function maxProfit(prices: number[]): number {
  let maxProfit = 0;
  let minPrice = prices[0];
  
  for (let i = 1; i < prices.length; i++) {
    maxProfit = Math.max(maxProfit, prices[i] - minPrice);
    minPrice = Math.min(minPrice, prices[i]);
  }
  
  return maxProfit;
}

Time: O(n), Space: O(1)

Using Kadane on differences:

function maxProfitKadane(prices: number[]): number {
  let maxProfit = 0;
  let currentProfit = 0;
  
  for (let i = 1; i < prices.length; i++) {
    const diff = prices[i] - prices[i - 1];
    currentProfit = Math.max(diff, currentProfit + diff);
    maxProfit = Math.max(maxProfit, currentProfit);
  }
  
  return maxProfit;
}

Pattern 5: Maximum Sum Subarray with At Most K Elements

Find maximum sum subarray with at most K elements.

function maxSumAtMostK(nums: number[], k: number): number {
  const n = nums.length;
  let maxSum = -Infinity;
  
  // Try all starting positions
  for (let start = 0; start < n; start++) {
    let currentSum = 0;
    
    // Try all lengths from 1 to k
    for (let len = 1; len <= k && start + len <= n; len++) {
      currentSum += nums[start + len - 1];
      maxSum = Math.max(maxSum, currentSum);
    }
  }
  
  return maxSum;
}

Time: O(n * k), Space: O(1)

Optimized with sliding window:

function maxSumAtMostKOptimized(nums: number[], k: number): number {
  let maxSum = -Infinity;
  
  // Fixed-size sliding window
  for (let windowSize = 1; windowSize <= k; windowSize++) {
    let windowSum = 0;
    
    // Initialize window
    for (let i = 0; i < windowSize; i++) {
      windowSum += nums[i];
    }
    maxSum = Math.max(maxSum, windowSum);
    
    // Slide window
    for (let i = windowSize; i < nums.length; i++) {
      windowSum = windowSum - nums[i - windowSize] + nums[i];
      maxSum = Math.max(maxSum, windowSum);
    }
  }
  
  return maxSum;
}

Time: O(n * k), Space: O(1)

Pattern 6: Maximum Alternating Sum

Find maximum alternating sum (add even-indexed, subtract odd-indexed).

function maxAlternatingSum(nums: number[]): number {
  let even = 0; // Maximum sum ending at even index
  let odd = 0;  // Maximum sum ending at odd index
  
  for (const num of nums) {
    const newEven = Math.max(even, odd + num);
    const newOdd = Math.max(odd, even - num);
    even = newEven;
    odd = newOdd;
  }
  
  return Math.max(even, odd);
}

Time: O(n), Space: O(1)

Pattern 7: Maximum Sum Non-Adjacent Elements

Find maximum sum of non-adjacent elements.

function maxSumNonAdjacent(nums: number[]): number {
  let include = 0; // Max sum including current
  let exclude = 0; // Max sum excluding current
  
  for (const num of nums) {
    const newInclude = exclude + num;
    const newExclude = Math.max(include, exclude);
    include = newInclude;
    exclude = newExclude;
  }
  
  return Math.max(include, exclude);
}

Time: O(n), Space: O(1)

Pattern 8: Maximum Sum After K Negations

Maximize array sum after at most K negations.

function maximizeSumAfterKNegations(nums: number[], k: number): number {
  // Sort to negate smallest negatives first
  nums.sort((a, b) => a - b);
  
  for (let i = 0; i < nums.length && k > 0; i++) {
    if (nums[i] < 0) {
      nums[i] = -nums[i];
      k--;
    } else {
      break;
    }
  }
  
  // If k is odd, negate smallest positive
  if (k % 2 === 1) {
    nums.sort((a, b) => a - b);
    nums[0] = -nums[0];
  }
  
  return nums.reduce((a, b) => a + b, 0);
}

Time: O(n log n), Space: O(1)

Pattern 9: Maximum Sum of 3 Non-Overlapping Subarrays

Find three non-overlapping subarrays of size K with maximum sum.

function maxSumOfThreeSubarrays(nums: number[], k: number): number[] {
  const n = nums.length;
  const prefix = new Array(n + 1).fill(0);
  
  // Build prefix sum
  for (let i = 0; i < n; i++) {
    prefix[i + 1] = prefix[i] + nums[i];
  }
  
  // left[i] = best starting index for subarray ending at or before i
  const left = new Array(n).fill(0);
  let bestSum = 0;
  for (let i = k - 1; i < n; i++) {
    const sum = prefix[i + 1] - prefix[i - k + 1];
    if (sum > bestSum) {
      bestSum = sum;
      left[i] = i - k + 1;
    } else {
      left[i] = left[i - 1];
    }
  }
  
  // right[i] = best starting index for subarray starting at or after i
  const right = new Array(n).fill(0);
  bestSum = 0;
  for (let i = n - k; i >= 0; i--) {
    const sum = prefix[i + k] - prefix[i];
    if (sum >= bestSum) {
      bestSum = sum;
      right[i] = i;
    } else {
      right[i] = right[i + 1];
    }
  }
  
  // Try all middle subarray positions
  let maxSum = 0;
  const result: number[] = [];
  
  for (let i = k; i <= n - 2 * k; i++) {
    const l = left[i - 1];
    const r = right[i + k];
    const sum = 
      (prefix[l + k] - prefix[l]) +
      (prefix[i + k] - prefix[i]) +
      (prefix[r + k] - prefix[r]);
    
    if (sum > maxSum) {
      maxSum = sum;
      result[0] = l;
      result[1] = i;
      result[2] = r;
    }
  }
  
  return result;
}

Time: O(n), Space: O(n)

Pattern 10: Maximum Sum Rectangle in 2D Matrix

Find maximum sum rectangle in 2D matrix using Kadane.

function maxSumRectangle(matrix: number[][]): number {
  const rows = matrix.length;
  const cols = matrix[0].length;
  let maxSum = -Infinity;
  
  // Try all left columns
  for (let left = 0; left < cols; left++) {
    const temp = new Array(rows).fill(0);
    
    // Try all right columns
    for (let right = left; right < cols; right++) {
      // Add column to temp
      for (let i = 0; i < rows; i++) {
        temp[i] += matrix[i][right];
      }
      
      // Apply Kadane's algorithm on temp array
      let currentSum = temp[0];
      let maxSubarraySum = temp[0];
      
      for (let i = 1; i < rows; i++) {
        currentSum = Math.max(temp[i], currentSum + temp[i]);
        maxSubarraySum = Math.max(maxSubarraySum, currentSum);
      }
      
      maxSum = Math.max(maxSum, maxSubarraySum);
    }
  }
  
  return maxSum;
}

Time: O(cols² * rows), Space: O(rows)

Explanation: For each left-right column pair, compress columns into 1D array and apply Kadane's algorithm.

Pattern 11: Maximum Sum with No Two Elements Adjacent

House Robber problem - maximize sum with no adjacent elements.

function rob(nums: number[]): number {
  let prev2 = 0; // Max sum two houses ago
  let prev1 = 0; // Max sum one house ago
  
  for (const num of nums) {
    const current = Math.max(prev1, prev2 + num);
    prev2 = prev1;
    prev1 = current;
  }
  
  return prev1;
}

Time: O(n), Space: O(1)

Pattern 12: Maximum Sum After Partitioning

Partition array into subarrays of at most size K, maximize sum.

function maxSumAfterPartitioning(arr: number[], k: number): number {
  const n = arr.length;
  const dp = new Array(n + 1).fill(0);
  
  for (let i = 1; i <= n; i++) {
    let maxVal = 0;
    
    // Try all partition sizes from 1 to k
    for (let j = 1; j <= k && i - j >= 0; j++) {
      maxVal = Math.max(maxVal, arr[i - j]);
      dp[i] = Math.max(dp[i], dp[i - j] + maxVal * j);
    }
  }
  
  return dp[n];
}

Time: O(n * k), Space: O(n)

When to Use Kadane's Algorithm

Use Kadane's algorithm when:

• Problem asks for maximum sum subarray
• Need contiguous subarray (not subsequence)
• Problem involves optimizing sum/product
• Dynamic programming with "extend or start fresh" decision
• O(n) time and O(1) space required
• Problem can be reduced to maximum subarray

Key distinction: Kadane finds contiguous subarray. For non-contiguous subsequence, use different DP approach.

Template (Classic Kadane)

function kadaneTemplate(nums: number[]): number {
  let maxSum = nums[0];
  let currentSum = nums[0];
  
  for (let i = 1; i < nums.length; i++) {
    // Extend previous subarray or start fresh
    currentSum = Math.max(nums[i], currentSum + nums[i]);
    maxSum = Math.max(maxSum, currentSum);
  }
  
  return maxSum;
}

Template (Kadane with Tracking)

function kadaneWithIndices(nums: number[]): [number, number, number] {
  let maxSum = nums[0];
  let currentSum = nums[0];
  let start = 0, end = 0, tempStart = 0;
  
  for (let i = 1; i < nums.length; i++) {
    if (currentSum < 0) {
      currentSum = nums[i];
      tempStart = i;
    } else {
      currentSum += nums[i];
    }
    
    if (currentSum > maxSum) {
      maxSum = currentSum;
      start = tempStart;
      end = i;
    }
  }
  
  return [maxSum, start, end];
}

Time and Space Complexity Summary

• Classic Kadane: O(n) time, O(1) space
• Maximum product: O(n) time, O(1) space
• Circular subarray: O(n) time, O(1) space
• 2D maximum rectangle: O(cols² * rows) time, O(rows) space
• Non-adjacent elements: O(n) time, O(1) space

Practice Tips

1. Core decision - Extend previous or start fresh?
2. Handle negatives - For product, track both min and max
3. Circular arrays - Consider wrapping around
4. Edge cases - All negative, single element, empty array
5. Track indices - If problem asks for subarray position

Common Mistakes

1. Initialization - Not setting initial values correctly
2. All negative - Not handling case where all elements are negative
3. Product - Forgetting to track minimum product
4. Circular - Not considering wrap-around case
5. Off-by-one - Index errors when tracking subarray bounds

Related Concepts

• Dynamic Programming - Kadane is a DP technique
• Sliding Window - Alternative for some subarray problems
• Prefix Sum - Can be combined with Kadane
• Greedy Algorithm - Kadane has greedy "extend or start" decision

Kadane's algorithm is essential for maximum subarray problems. Master this technique, and you'll efficiently solve a wide range of optimization problems in coding interviews.