A few days ago, I have been given a problem to find the sub-sequence within an array with which has a total sum of 0. Within array A[1-N], you have to find i and j such that

A[i] + A[i+1]... A[j] = 0; i <=j.

Ofcourse, the problem can be extended further to find the longest subsequence among all possible sub-sequences. Once you have the solution for first part, finding longest sub-sequence is no more a tricky job.

This is what I thought:

The idea is: If sum of elements from [i+1, j] is 0, then, after this subset, ith number would appear again at [j+1] position.

i.e. Sum(N[i] + N[i+1, j]) = N[j + 1], if N[i+1, j] = 0.

FindZeroSumSequence(Array):

{

1. Sum elements such that ith index has sum up to [0 -i] elements

For i = 1 to N

Array[i] += Array[i -1]

2. Find the first duplicate index from array

EndIndex = FindFirstDuplicateIndex(Array)

3. IF EndIndex > -1

Find the First index with value equal to Array[EndIndex]

For i = 0 to N

IF(Array[i] == Array[EndIndex]

StartIndex = i

Break

4. Return StartIndex and EndIndex as sub array indexes.

}

Running time of the algorithm is O(n) (though it slowly depends on the running time of FindFirstDuplicateIndex method which could be implemented in O(n) time).

A[i] + A[i+1]... A[j] = 0; i <=j.

Ofcourse, the problem can be extended further to find the longest subsequence among all possible sub-sequences. Once you have the solution for first part, finding longest sub-sequence is no more a tricky job.

This is what I thought:

The idea is: If sum of elements from [i+1, j] is 0, then, after this subset, ith number would appear again at [j+1] position.

i.e. Sum(N[i] + N[i+1, j]) = N[j + 1], if N[i+1, j] = 0.

FindZeroSumSequence(Array):

{

1. Sum elements such that ith index has sum up to [0 -i] elements

For i = 1 to N

Array[i] += Array[i -1]

2. Find the first duplicate index from array

EndIndex = FindFirstDuplicateIndex(Array)

3. IF EndIndex > -1

Find the First index with value equal to Array[EndIndex]

For i = 0 to N

IF(Array[i] == Array[EndIndex]

StartIndex = i

Break

4. Return StartIndex and EndIndex as sub array indexes.

}

Running time of the algorithm is O(n) (though it slowly depends on the running time of FindFirstDuplicateIndex method which could be implemented in O(n) time).