Я реализовал проблему массива Kadane Max Sub в javascript, но, похоже, в конечном итоге я всегда получаю 0 в консоли, хотя существуют более высокие числа (я понимаю, что он делает то, что делает, из-за цикла for из 0 - size где size = subarray size).
Итак, как мне правильно реализовать алгоритм?
Это также работает для всех положительных целых массивов?
Вы передаете n = 3 в качестве аргумента, а длина вашего массива равна 6. Я изменил ваш алгоритм, чтобы использовать length:
function SubSequence(a){
var now = 0,prev =0;
for(var i = 0;i < a.length;i++){
prev = Math.max(0,prev + a[i]);
now = Math.max(prev,now);
}
return now;
}
console.log(SubSequence([-1,-2,-3,4,6,7]));
и дает 17.
Это также работает для всех положительных целых массивов?
Да, тогда он даст сумму всех элементов в массиве.
Если вам нужна максимальная подпоследовательность длины 3, используйте
function SubSequence(a,n){
var now = 0;
for(var i = 0; i < n; i++) {
now += a[i];
}
var best = now;
for(var i = n;i < a.length;i++) {
now += a[i] - a[i-n];
best = Math.max(now,best);
}
return best;
}
console.log(SubSequence([-1,-2,-3,4,6,7,1,4],3));
лучше всего 4+6+7, а 4+6+7+1+4 не допускается.
В информатике задача максимального подмассива — это задача найти непрерывный подмассив в одномерном массиве чисел (содержащем хотя бы одно положительное число), который имеет наибольшую сумму.
Алгоритм Кадане - это метод поиска решения вышеуказанной проблемы.
Простая идея алгоритма Кадане состоит в том, чтобы искать все положительные непрерывные сегменты массива (скажем, max_ending_here). И отслеживайте максимальный суммарный непрерывный сегмент среди всех положительных сегментов (скажем, max_so_far). Каждый раз, когда мы получаем положительную сумму, сравниваем ее с max_so_far и обновляем max_so_far, если она больше, чем max_so_far.
Алгоритм не работает для всех отрицательных чисел. Он просто возвращает 0, если все числа отрицательные. Для обработки этого мы можем добавить дополнительную фазу перед фактической реализацией. Фаза будет выглядеть, если все числа отрицательные, если они есть, она вернет максимальное из них (или наименьшее по абсолютному значению)
То, что вы опубликовали, является реализацией в случае, когда все числа в массиве отрицательны. Это не относится к фактическому алгоритму, а просто к дополнительной фазе. Алгоритм Кадане для массива 1D:
this is the general algorithm.
Initialize:
max_so_far = 0
max_ending_here = 0
Loop for each element of the array
(a) max_ending_here = max_ending_here + a[i]
(b) if(max_ending_here < 0)
max_ending_here = 0
(c) if(max_so_far < max_ending_here)
max_so_far = max_ending_here
return max_so_far
надеюсь, что это объяснение будет полезным для вас.
Однако очень поздно ответить на этот вопрос, на всякий случай, если это кому-нибудь поможет, моя попытка решить проблему, включая случай, когда все элементы массива отрицательные.
let allPositives = arr => arr.every(n => n > 0)
let allNegatives = arr => arr.every(n => n < 0)
let sum = arr => arr.reduce((curr_max, max_so_far) => curr_max + max_so_far, 0)
var getMaxArrNumber = function (arr) {
return Math.max.apply(null, arr);
}
var maxSequence = function(arr){
if(arr.length === 0 ) return 0;
if(allNegatives(arr)) return getMaxArrNumber(arr);
if(allPositives(arr)) return sum(arr);
var curr_max = 0, max_so_far = 0;
for(var i = 0; i < arr.length; i++){
curr_max = Math.max(0, curr_max + arr[i]);
max_so_far = Math.max(curr_max, max_so_far);
}
return max_so_far;
}
