Алгоритм Кадане можно рассматривать и как жадный, и как DP. Как мы видим, мы сохраняем текущую сумму целых чисел, и когда она становится меньше 0, мы сбрасываем ее до 0 (жадная часть). Это связано с тем, что продолжение с отрицательной суммой намного хуже, чем перезапуск с новым диапазоном. Теперь его также можно рассматривать как DP, на каждом этапе у нас есть 2 варианта: либо взять текущий элемент и продолжить с предыдущей суммой, либо перезапустить новый диапазон. Оба варианта учитываются при реализации.
Array = [-2, -3, 4, -1, -2, 1, 5, -3]
var maxSubArray = function(nums) {
let sum = 0;
let maxSum = -Infinity;
if(nums.length === 0) return 0;
if(nums.length === 1) return nums[0]
for(let i = 0;i<nums.length;i++){
sum+=nums[i];
maxSum = Math.max(maxSum,sum);
if(sum < 0) sum = 0;
}
return maxSum;
};
Этот алгоритм можно рассматривать как простой/тривиальный пример динамического программирования.
Алгоритмическая парадигма:динамическое программирование | На)
function
maxSubArraySum(a,size) {
let max_so_far = a[0]; let curr_max = a[0];
for
(let i = 1; i < size; i++) { curr_max = Math.max(a[i], curr_max + a[i]); max_so_far = Math.max(max_so_far, curr_max); }
return
max_so_far;
}
Ссылка,