Работает ли алгоритм Max Sub Array от Kadane для всех целых положительных чисел?

Question

Я реализовал проблему с массивом Max Sub в Kavane в javascript, но, похоже, в итоге я всегда получаю 0 в консоли, хотя существуют большие числа (я понимаю, что он делает то, что делает из-за цикла for из 0 - size где size = subarray size).

• Так как же правильно реализовать алгоритм?

• Это также работает для всего массива положительных целых чисел?

JsBin

http://jsbin.com/ajivan/edit

Answer 1

Вы передаете 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 не допускается.

Answer 2

В компьютерных науках проблема максимального подмассива - это задача поиска смежного подмассива в одномерном массиве чисел (содержащем по крайней мере одно положительное число), который имеет наибольшую сумму.

Алгоритм Кадане - это способ найти решение вышеуказанной проблемы.

Простая идея алгоритма Кадане состоит в том, чтобы искать все положительные смежные сегменты массива (скажем, max_ending_here). И отслеживать максимальную сумму непрерывного сегмента среди всех положительных сегментов (скажем, max_so_far). Каждый раз, когда мы получаем положительную сумму, сравниваем ее с max_so_far и обновляем max_so_far, если она больше, чем max_so_far.

Алгоритм не работает для всех отрицательных чисел. Он просто возвращает 0, если все числа отрицательны. Для обработки этого мы можем добавить дополнительную фазу перед фактической реализацией. Фаза проверяет, являются ли все числа отрицательными, если они есть, она возвращает максимальное из них (или наименьшее по абсолютной величине)

То, что вы опубликовали, является реализацией в случае, когда все числа в массиве отрицательны. Это не относится к фактическому алгоритму, а просто к дополнительной фазе. Алгоритм Кадане для 1 D массива:

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

надеюсь, что это объяснение будет полезно для вас.

Answer 3

Однако здесь очень поздно и по этому вопросу, на всякий случай, если это кому-нибудь поможет, моя попытка решить проблему, включая случай, когда все элементы массива являются отрицательными.

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;
}