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).
