Алгоритм Кадане

Сегодня решала задачу на алгоритм Кадане, главная идея которого - нахождение подмассива с максимальной суммой чисел в массиве.

Вот ссылка на задачу на leetcode.

Уровень, кстати, medium. Но, кажется, все довольно нативно.

Ограничения:
- Значения чисел в массиве: от -10^4 до + 10^5
- Длина массива: от 1 до 10^4

Ну, собственно, условие - найти подмассив с максимальной суммой чисел в массиве.

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

Реализация:
1. Заводим две переменные под текущую сумму и под максмальную сумму, инициализируя их первым элементом массива, т.к. это минимально возможный подмассив.
2. Начинаем итерацию по массива со 2-ого элемента:
- Проверяем, продолжать ли текущий подмассив (добавив текущий элемент к currentSum), или начать новый подмассив с текущего элемента
- Если текущая сумма становится отрицательной, алгоритм фактически "сбрасывает" её и начинает новый подмассив с текущего элемента.
- Обновляем максимальную сумму
3. Возвращаем максимальную сумму.

Итак, код:

public int maxSubArray(int[] nums) {
    int currentSum = nums[0];
    int maxSum = nums[0];
    for (int i = 1; i < nums.length; i++) {
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        maxSum = Math.max(maxSum, currentSum);
        }
    return maxSum;
}

А если не хочется использовать Math.max, то можно через if-ы (только тут currentSum = 0 изначально, иначе сломается)

public int maxSubArray(int[] nums) {
    int currentSum = 0, maxSum = nums[0];
    for (int i = 0; i < nums.length; i++) {
        currentSum += nums[i];
        if (currentSum > maxSum) maxSum = currentSum;
        if (currentSum < 0) currentSum = 0;
    }
    return maxSum;
}

Временная сложность: О(n) - один раз проходимся по массиву
Пространственная сложность: O(1) - только память под константы.