寻找最长的零和子序列

Question

警告：这不是 "finding the longest subarray which sums to zero" 问题的实例

我想知道是否有任何算法可以找到序列中总和为零的最大子序列（即元素可以连续或不连续）的长度，例如

S = {1, 4, 6, -1, 2, 8, -2}
     ^         ^  ^      ^
maximum length = 4

我搜索过，但没有找到

Answer 1

这是 subset sum 问题的细微变化。

让d[i] = maximum length of a subsequence that sums to i。最初，这都是零。如果你的数字都是正数，你可以这样做：

s = 0
for i = 1 to n:
    s += a[i]
    for j = s down to a[i]:
        d[j] = max(d[j],               <- keep j as it is
                   d[j - a[i]] + 1     <- add a[i] to j - a[i], obtaining sum j
                  )

return ???

但是，这并没有考虑到有负面因素的可能性。为了处理这些，您可以使用两个字典而不是数组：

a = [1, 4, 6, -1, 2, 8, -2] # the input array
d1 = {0: 0} # first dictionary: explicitly initialize d[0] = 0
d2 = {0: 0} # second dictionary is the same initially
n = len(a) # the length of the input array

for i in range(n): # for each index of the input array
    for j in d1: # for each value in the first dictionary

        x = 0
        if j + a[i] in d2: # if we already have answer for j + a[i] 
                           # in the second dictionary, we store it
            x = d2[j + a[i]]

        d2[j + a[i]] = max(x, d1[j] + 1) # add a[i] to the j in the first dictionary 
                                         # and get a new value in the second one,
                                         # or keep the existing one in the second dictionary,
                                         # if it leads to a longer subsequence


    d1 = dict(d2) # copy the second dictionary into the first.
                  # We need two dictionaries to make sure that 
                  # we don't use the same element twice

print(d1[0]) # prints 4

如果你添加一些常量，你也可以用数组实现这个，这样你就不会访问负索引，但字典更干净。

时间复杂度为 O(n*S)，其中 S 是数组中所有数字的总和，n 是数组中元素的数量。

Answer 2

还有一个使用动态规划和函数式编程的解决方案。在 javascript:

function maxSumZeroAcc(arr, sumS, nbElt) {
//returns nbElt + the size of the longest sequence summing to sumS
  if(arr.length === 0) {
    return (sumS===0)?nbElt:0;
  }
  else {
    return Math.max(maxSumZeroAcc(arr.slice(1), sumS, nbElt),maxSumZeroAcc(arr.slice(1), sumS-arr[0], nbElt+1));
  }
}

function maxSumZero(arr) {
//simply calls the previous function with proper initial parameters
  return maxSumZeroAcc(arr, 0, 0);
}

var myS = [1,4,6,-1,2,8,-2];
console.log(maxSumZero(myS));//returns 4

代码的核心是 maxSumZeroAcc(arr, sumS, nbElt) 函数 returns nbElt 增加了 arr 中最长序列的大小，总和为 sumS -- sumS和nbElt是函数maxSumZero中设置的两个辅助参数。

maxSumZeroAcc 背后的想法是，我们正在寻找的最大值是应用于数组尾部的 maxSumZeroAcc 的最大值（我们简单地丢弃第一个元素）或 maxSumZeroAcc(.,sumS-arr[0],nbElt+1) 应用于数组的尾部（我们考虑第一个元素，而不是找到 sumS 的元素总和，我们寻找第一个元素减去 sumS 的元素总和).

这个解决方案写起来很短，也很容易理解，但复杂度很差，在 O(2^n) 中，其中 n 是数组的大小。

寻找最长的零和子序列

Finding the longest zero-sum subsequence

language-agnostic

algorithm

警告：这不是 "finding the longest subarray which sums to zero" 问题的实例