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

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

Проблема

Нужно найти непрерывный подмассив (contiguous subarray) с наибольшей суммой элементов. Важно: подмассив должен быть непрерывным, то есть состоять из элементов подряд.

Примеры:

• [-2,1,-3,4,-1,2,1,-5,4] → ответ 6 (подмассив [4,-1,2,1])
• [1] → ответ 1 (один элемент)
• [5,4,-1,7,8] → ответ 23 (весь массив)
• [-3,-2,-1] → ответ -1 (максимальный из отрицательных)

Наивный подход: Brute Force

public class MaxSubarrayBruteForce {
    public static int maxSubarray(int[] nums) {
        int maxSum = Integer.MIN_VALUE;
        
        // Пробуем каждую возможную пару start и end
        for (int i = 0; i < nums.length; i++) {
            int currentSum = 0;
            // От позиции i до конца массива
            for (int j = i; j < nums.length; j++) {
                currentSum += nums[j];
                maxSum = Math.max(maxSum, currentSum);
            }
        }
        
        return maxSum;
    }
}

// Сложность: O(n²) — слишком медленно для больших массивов

Оптимальное решение: Алгоритм Кадане

Идея: в каждой позиции решаем, продолжать ли текущий подмассив или начать с нового элемента.

public class MaxSubarrayKadane {
    public static int maxSubarray(int[] nums) {
        // Инициализируем обе переменные первым элементом
        int maxSum = nums[0];
        int currentSum = nums[0];
        
        // Проходим по остальным элементам
        for (int i = 1; i < nums.length; i++) {
            // Ключевая идея: для каждого элемента решаем:
            // начать новый подмассив с этого элемента (nums[i])
            // или продолжить текущий подмассив (currentSum + nums[i])
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            
            // Обновляем глобальный максимум
            maxSum = Math.max(maxSum, currentSum);
        }
        
        return maxSum;
    }
    
    public static void main(String[] args) {
        // Тест 1
        int[] arr1 = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubarray(arr1)); // 6
        
        // Тест 2
        int[] arr2 = {1};
        System.out.println(maxSubarray(arr2)); // 1
        
        // Тест 3
        int[] arr3 = {5, 4, -1, 7, 8};
        System.out.println(maxSubarray(arr3)); // 23
        
        // Тест 4: все отрицательные
        int[] arr4 = {-3, -2, -1};
        System.out.println(maxSubarray(arr4)); // -1
    }
}

Пошаговое объяснение с примером

Рассмотрим массив: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Шаг 0: инициализация
  maxSum = -2, currentSum = -2

Шаг 1: i=1, num=1
  currentSum = max(1, -2+1) = max(1, -1) = 1
  maxSum = max(-2, 1) = 1
  
Шаг 2: i=2, num=-3
  currentSum = max(-3, 1+(-3)) = max(-3, -2) = -2
  maxSum = max(1, -2) = 1
  
Шаг 3: i=3, num=4
  currentSum = max(4, -2+4) = max(4, 2) = 4
  maxSum = max(1, 4) = 4
  
Шаг 4: i=4, num=-1
  currentSum = max(-1, 4+(-1)) = max(-1, 3) = 3
  maxSum = max(4, 3) = 4
  
Шаг 5: i=5, num=2
  currentSum = max(2, 3+2) = max(2, 5) = 5
  maxSum = max(4, 5) = 5
  
Шаг 6: i=6, num=1
  currentSum = max(1, 5+1) = max(1, 6) = 6  ← Нашли максимум!
  maxSum = max(5, 6) = 6
  
Шаг 7: i=7, num=-5
  currentSum = max(-5, 6+(-5)) = max(-5, 1) = 1
  maxSum = max(6, 1) = 6
  
Шаг 8: i=8, num=4
  currentSum = max(4, 1+4) = max(4, 5) = 5
  maxSum = max(6, 5) = 6

РЕЗУЛЬТАТ: 6 ✓

С отслеживанием индексов (найти сам подмассив)

Часто нужно не только значение, но и сами элементы подмассива:

public class MaxSubarrayWithIndices {
    static class Result {
        int maxSum;
        int startIndex;
        int endIndex;
        
        Result(int maxSum, int start, int end) {
            this.maxSum = maxSum;
            this.startIndex = start;
            this.endIndex = end;
        }
    }
    
    public static Result maxSubarray(int[] nums) {
        int maxSum = nums[0];
        int currentSum = nums[0];
        int tempStart = 0;  // начало текущего подмассива
        int startIndex = 0; // начало макс подмассива
        int endIndex = 0;   // конец макс подмассива
        
        for (int i = 1; i < nums.length; i++) {
            // Если лучше начать с нового элемента
            if (nums[i] > currentSum + nums[i]) {
                currentSum = nums[i];
                tempStart = i;  // новое начало
            } else {
                currentSum += nums[i];
            }
            
            // Обновляем максимум
            if (currentSum > maxSum) {
                maxSum = currentSum;
                startIndex = tempStart;
                endIndex = i;
            }
        }
        
        return new Result(maxSum, startIndex, endIndex);
    }
    
    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        Result result = maxSubarray(arr);
        
        System.out.println("Максимальная сумма: " + result.maxSum);
        System.out.println("С индекса " + result.startIndex + " до " + result.endIndex);
        
        // Выводим сам подмассив
        System.out.print("Подмассив: [");
        for (int i = result.startIndex; i <= result.endIndex; i++) {
            System.out.print(arr[i]);
            if (i < result.endIndex) System.out.print(", ");
        }
        System.out.println("]");
        
        // Вывод:
        // Максимальная сумма: 6
        // С индекса 3 до 6
        // Подмассив: [4, -1, 2, 1]
    }
}

Динамическое программирование: другой взгляд

Алгоритм Кадане можно рассмотреть как DP:

dp[i] = максимальная сумма подмассива, заканчивающегося в позиции i

dp[i] = max(nums[i], dp[i-1] + nums[i])

Ответ: max(dp[0], dp[1], ..., dp[n-1])

public class MaxSubarrayDP {
    public static int maxSubarray(int[] nums) {
        // dp[i] = макс сумма подмассива, заканчивающегося в i
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int maxSum = dp[0];
        
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(nums[i], dp[i-1] + nums[i]);
            maxSum = Math.max(maxSum, dp[i]);
        }
        
        return maxSum;
    }
}

// Но эта версия использует O(n) памяти
// Версия Кадане выше экономит память, используя только O(1)

Анализ сложности

Временная сложность: O(n)

• Один проход через весь массив
• Каждый элемент посещается ровно один раз

Пространственная сложность: O(1)

• Используем только две переменные: maxSum и currentSum
• Не используем дополнительные структуры данных

Особые случаи

// Все отрицательные числа
int[] arr1 = {-3, -2, -1};
System.out.println(maxSubarray(arr1)); // -1 (максимальный элемент)

// Один элемент
int[] arr2 = {5};
System.out.println(maxSubarray(arr2)); // 5

// Смешанные числа
int[] arr3 = {-1, 0, -2};
System.out.println(maxSubarray(arr3)); // 0 (пустой подмассив невозможен, берём 0)

// Большой массив
int[] arr4 = new int[1_000_000];
for (int i = 0; i < arr4.length; i++) {
    arr4[i] = (i % 2 == 0) ? 1 : -1;
}
System.out.println(maxSubarray(arr4)); // 1 (O(n) — очень быстро)

Практическое применение

1. Финансы: найти период с максимальной прибылью
2. Обработка сигналов: найти интервал с максимальной амплитудой
3. Анализ данных: найти подпериод с максимальным значением метрики
4. Игры: найти период с максимальным заработком очков

Вывод

Алгоритм Кадане — это элегантное решение задачи о максимальной сумме подмассива:

• Временная сложность: O(n) — линейная
• Пространственная сложность: O(1) — константная
• Идея: в каждой позиции решаем, продолжить подмассив или начать с нуля
• Ключ: currentSum = max(num, currentSum + num)

Это классический пример жадного алгоритма (greedy algorithm) и динамического программирования, который часто спрашивают на собеседованиях.