CODEWITHSUNDEEP
algorithmlanguage-agnostic
Dean
Dean

Reputation: 6950

Finding the longest zero-sum subsequence

WARNING: this is NOT an instance of "finding the longest subarray which sums to zero" problem

I'm wondering if there's any algorithm to find the length of the maximum subsequence (i.e. elements can be contiguous or not) which sums to zero in a sequence, e.g.

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

I searched for it but I couldn't find any

Upvotes: 2

Views: 2148

Answers (2)

isanco
isanco

Reputation: 86

There is also a solution using dynamic programming and functional progamming. In 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

The core of the code is the function maxSumZeroAcc(arr, sumS, nbElt) that returns nbElt augmented of the size of the longest sequence in arr summing to sumS -- sumS and nbElt being two auxiliairy parameters set up in the function maxSumZero.

The idea behind maxSumZeroAcc is that the max we are looking for is either the max of maxSumZeroAcc applied to the tail of the array (we simply discard the first element) or of maxSumZeroAcc(.,sumS-arr[0],nbElt+1) applied to the tail of the array (we take into accound the first element and instead of finding a sum of element to sumS, we look for sum of elements to sumS diminished of the first element).

This solution is rather short to write down and quite easy to understand but the complexity is pretty bad and is in O(2^n), where n is the size of the array.

Upvotes: 0

IVlad
IVlad

Reputation: 43477

It's a slight variation on the subset sum problem.

Let d[i] = maximum length of a subsequence that sums to i. Initially, this is all zero. If your numbers were all positive, you could do:

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 ???

However, this does not account for the possibility of having negative elements. In order to handle those, you can use two dictionaries instead of an array:

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

You can also implement this with arrays if you add some constants so you don't access negative indexes, but dictionaries are cleaner.

Time complexity will be O(n*S) where S is the sum of all numbers in the array and n the number of elements in the array.

Upvotes: 2

Related Questions