53. Maximum Subarray

Задача

Дан массив nums. Найдите подмассив с наибольшей суммой и верните эту сумму (алгоритм Кадана).

Примеры

Пример 1

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6

Пояснение

Подмассив [4,-1,2,1] имеет наибольшую сумму 6.

Пример 2

Input: nums = [1]
Output: 1

Пояснение

Подмассив [1] имеет наибольшую сумму 1.

Пример 3

Input: nums = [5,4,-1,7,8]
Output: 23

Пояснение

Подмассив [5,4,-1,7,8] имеет наибольшую сумму 23.

Решение

Решение

/**
 * Находит подмассив с максимальной суммой (алгоритм Кадане)
 * Временная сложность: O(n)
 * Пространственная сложность: O(1)
 */
var maxSubArray = function(nums) {
    let currentSum = 0;
    let maxSum = -Infinity;
 
    for (let num of nums) {
        // Даже если num очень отрицательное, брать только его всё равно лучше, чем отрицательная_сумма + num
        currentSum = currentSum < 0 ? num : currentSum + num;
        maxSum = Math.max(maxSum, currentSum);
    }
 
    return maxSum;
};