卡登最大子数组算法适用于所有的正整数数组吗？

Question

我在JavaScript中实现了Kadane的最大子数组问题，但似乎总是在控制台中得到0，即使存在更高的数字（我理解它之所以这样做是因为for循环从0-size，其中size=subarray size）。那么我该如何正确地实现算法呢？它是否也适用于所有正整数数组？

JsBin: http://jsbin.com/ajivan/edit#javascript,live

- Deeptechtons

Answer 1

你在将长度为6的数组作为参数传递给n=3。我改变了你的算法，使用length代替了它：

你正在将长度为6的数组作为参数传递给n=3。我已经更改了你的算法，使用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。

- sdcvvc

---

@sdcwc 我怎么知道子数组的大小，使得它们的和为17？它总是等于数组的长度吗？我认为你可以指定算法扫描的子数组大小，并告诉最大和的数组。 - Deeptechtons

Deeptechtons：该算法不考虑长度，仅告诉您最大总和。您想知道在此示例中结果的长度为3，还是要找到具有最大总和的长度为3的中缀？ - sdcvvc

Answer 2

在计算机科学中，最大子数组问题是查找一个一维数字数组（包含至少一个正数）中具有最大总和的连续子数组的任务。

Kadane算法是解决上述问题的一种方法。

Kadane算法的简单思想是查找数组的所有正连续段（假设为max_ending_here），并跟踪所有正段中的最大总和连续段（假设为max_so_far）。每次我们得到一个正数总和就将其与max_so_far比较，并在它大于max_so_far时更新max_so_far。

该算法不能处理所有负数。如果所有数字都是负数，则只会返回0。为了处理这个问题，在实际实现之前可以添加一个额外的阶段。该阶段将查看所有数字是否都为负数，如果是，则返回它们的最大值（或绝对值最小的值）。

你所发布的内容是在数组中所有数字都为负数时的实现。它不是指实际算法，而只是一个额外的阶段。1D数组的Kadane算法如下：

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

希望这个解释对你有所帮助。

- myk.

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

- Rohan_Paul