The sequence could still have a subsequence of sum 0 even if the sum of the maximum sum subsequence is greater than 0.
Take for instance: -2 -1 0 1 2 If 0 is in an element of the sequence, you're done. Let b[i] = the sum of the first i elements in the sequence. If b[i] = 0, for some i you're done as well. If b[i] != b[j] for all i != j, there is no subsequence of sum 0. Why? Suppose there is a subsequence (i, j) of sum 0. The sum of the subsequence (i, j) = b[j] - b[i - 1] = 0 => b[j] = b[i - 1]. Contradiction. Conversely, if b[i] = b[j] for some i, j, then the subsequence (i + 1, j) has sum 0. Therefore you need to check if two elements of the array b are equal. This can be easily done in O(n). --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
