I was assuming that the original poster wanted an algorithm for a
continuous range subsequence which I should have called a substring :).
Thanks KS.
How big is the sum of the positive elements of the sequence? Subset-sum
is NP-complete, and the standard DP solution doesn't fit in the
original pos
If the problem is finding whether a _subsequence_ adds to 0, its a
subset sum problem, which can be solved using dynamic programming. If
the problem is finding whether a _substring_ adds to 0, then you can
follow what others have said in the thread.
--~--~-~--~~~---~
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 don
just searched,
http://www.cs.ucla.edu/classes/spring04/cs32/lectures/maxSum/maxSeqSum2.pdf
it gives an O(n) solution(page 2). in this case just check if MaxSum=0
On 11/17/06, Idris <[EMAIL PROTECTED]> wrote:
>
>
> can u pls explain it?:-)
>
>
> >
>
--~--~-~--~~~--
sorry it sum not some:-)
--~--~-~--~~~---~--~~
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
sorry it sum note some:-)
--~--~-~--~~~---~--~~
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 [EMAI
can u pls explain it?:-)
--~--~-~--~~~---~--~~
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 [E
search for "maximum subsequence problem". urs is a special case of that.
On 11/16/06, Idris <[EMAIL PROTECTED]> wrote:
>
>
> You can use N space.:-)
>
>
> >
>
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algori
