Максимальная сумма подмассива (алгоритм Кадана)

Решение: Максимальная сумма подмассива (Алгоритм Кадана)

История и значение

Алгоритм Кадана, разработанный Джеем Кадейном в 1977 году, — один из классических примеров динамического программирования. Он решает задачу о максимальной сумме подмассива за линейное время, что считается оптимальным решением для этой проблемы.

Основная идея

Алгоритм поддерживает две переменные:

• currentSum — максимальная сумма подмассива, заканчивающегося в текущей позиции
• maxSum — глобально максимальная сумма найденная до текущего момента

На каждой итерации принимаем решение: либо расширить текущий подмассив, включив текущий элемент, либо начать новый подмассив с текущего элемента.

Базовое решение

function maxSubarraySum(arr) {
  let currentSum = arr[0];
  let maxSum = arr[0];
  
  for (let i = 1; i < arr.length; i++) {
    // Решаем: продолжить подмассив или начать заново
    currentSum = Math.max(arr[i], currentSum + arr[i]);
    // Обновляем глобальный максимум
    maxSum = Math.max(maxSum, currentSum);
  }
  
  return maxSum;
}

Решение с отслеживанием индексов (бонус)

function maxSubarraySum(arr) {
  let maxSum = arr[0];
  let currentSum = arr[0];
  
  let maxStart = 0;
  let maxEnd = 0;
  let currentStart = 0;
  
  for (let i = 1; i < arr.length; i++) {
    // Если начало нового подмассива лучше продолжения старого
    if (arr[i] > currentSum + arr[i]) {
      currentSum = arr[i];
      currentStart = i; // Новое начало
    } else {
      currentSum += arr[i];
    }
    
    // Если нашли новый максимум
    if (currentSum > maxSum) {
      maxSum = currentSum;
      maxStart = currentStart;
      maxEnd = i;
    }
  }
  
  return {
    sum: maxSum,
    subarray: arr.slice(maxStart, maxEnd + 1),
    startIndex: maxStart,
    endIndex: maxEnd
  };
}

TypeScript версия

interface MaxSubarrayResult {
  sum: number;
  subarray: number[];
  startIndex: number;
  endIndex: number;
}

function maxSubarraySum(arr: number[]): MaxSubarrayResult {
  if (arr.length === 0) {
    throw new Error("Array must contain at least one element");
  }
  
  let maxSum = arr[0];
  let currentSum = arr[0];
  let maxStart = 0;
  let maxEnd = 0;
  let currentStart = 0;
  
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > currentSum + arr[i]) {
      currentSum = arr[i];
      currentStart = i;
    } else {
      currentSum += arr[i];
    }
    
    if (currentSum > maxSum) {
      maxSum = currentSum;
      maxStart = currentStart;
      maxEnd = i;
    }
  }
  
  return {
    sum: maxSum,
    subarray: arr.slice(maxStart, maxEnd + 1),
    startIndex: maxStart,
    endIndex: maxEnd
  };
}

Пошаговый разбор примера

// Массив: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
// Инициализация: currentSum = -2, maxSum = -2

// i=1: currentSum = max(1, -2+1) = 1, maxSum = 1
// i=2: currentSum = max(-3, 1-3) = -2, maxSum = 1
// i=3: currentSum = max(4, -2+4) = 4, maxSum = 4
// i=4: currentSum = max(-1, 4-1) = 3, maxSum = 4
// i=5: currentSum = max(2, 3+2) = 5, maxSum = 5
// i=6: currentSum = max(1, 5+1) = 6, maxSum = 6 ← МАКСИМУМ
// i=7: currentSum = max(-5, 6-5) = 1, maxSum = 6
// i=8: currentSum = max(4, 1+4) = 5, maxSum = 6

// Результат: 6

Примеры использования

// Классический пример
console.log(maxSubarraySum([-2, 1, -3, 4, -1, 2, 1, -5, 4]));
// { sum: 6, subarray: [4, -1, 2, 1], startIndex: 3, endIndex: 6 }

// Один элемент
console.log(maxSubarraySum([1]));
// { sum: 1, subarray: [1], startIndex: 0, endIndex: 0 }

// Все отрицательные
console.log(maxSubarraySum([-1, -2, -3]));
// { sum: -1, subarray: [-1], startIndex: 0, endIndex: 0 }

// Все положительные
console.log(maxSubarraySum([5, 4, -1, 7, 8]));
// { sum: 23, subarray: [5, 4, -1, 7, 8], startIndex: 0, endIndex: 4 }

// Смешанные
console.log(maxSubarraySum([-2, -3, 4, -1, -2, 1, 5, -3]));
// { sum: 7, subarray: [4, -1, -2, 1, 5], startIndex: 2, endIndex: 6 }

Визуализация алгоритма

Массив:     [-2,  1, -3,  4, -1,  2,  1, -5,  4]
Текущая:    [-2,  1, -2,  4,  3,  5,  6,  1,  5]
Максимум:   [-2,  1,  1,  4,  4,  5,  6,  6,  6] ← Ответ

Динамическое программирование подход

// Формула DP:
// dp[i] = максимальная сумма подмассива, заканчивающегося в индексе i
// dp[i] = max(arr[i], dp[i-1] + arr[i])

function maxSubarraySum(arr) {
  const dp = new Array(arr.length);
  dp[0] = arr[0];
  
  for (let i = 1; i < arr.length; i++) {
    dp[i] = Math.max(arr[i], dp[i - 1] + arr[i]);
  }
  
  return Math.max(...dp);
}

Сравнение подходов

Применение в реальной жизни

• Финансы: находить период с наибольшей прибылью
• Анализ данных: максимальный рост метрики за период
• Алгоритмы: основа для более сложных оптимизаций

Ключевые моменты

• Линейная сложность: один проход по массиву
• Константная память: не зависит от размера входа
• Динамическое программирование: оптимальная подструктура
• Greedy выбор: на каждом шаге выбираем лучший вариант