[Leet Code] Максимальный подмассив

Проблема

Учитывая целочисленный массив nums, найдите непрерывный подмассив (содержащий хотя бы одно число), который имеет наибольшую сумму, и верните его сумму.

Примеры

Input : [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output : 6
Explanation : [4, -1, 2, 1] has the largest sum = 6.

Примечание

Будет найдено решение с временной сложностью O (n), которое не должно генерировать суммы целых подмассивов ввода.

Решение

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

var maxSubArray = function(nums) {
    let current = 0; 
    let maxNum = nums[0];
    
    for(let i = 0; i < nums.length; i++) {
        current = Math.max(current + nums[i], nums[i]);
        maxNum = Math.max(current, maxNum);
    }
    
    return maxNum; 
    
};

Визуализированные массивы для вашего удобства

i) Since current = 0, for index 0 it will be Math.max(-2, -2);
ii) Now that both current and maxNum are initialized to 0, i will be incremented - with Math.max(-1, 1) the current will be initialized to 1 and so as the maxNum
iii) Remember to either to initialize current to nums[i] + current OR nums[i] based on the maximum output. 

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