On Oct 17, 1:36 pm, "Channa Bankapur" <[EMAIL PROTECTED]>
wrote:
> Kannan must have meant for "subsequence". Without looking into Kadane's
> algo, I was trying to put constraints away from brute-force.
> 1. Terminal numbers of the subsequence has to be non-negative. Proof is - if
> a terminal number is negative, just exclude that and you'll get a higher
> sum.
>
> Regards,
> Channa
>
> On 10/17/07, Muntasir Azam Khan <[EMAIL PROTECTED]> wrote:
>
>
>
>
>
> > On Oct 17, 2:31 am, "Vinay Chilakamarri"
> > <[EMAIL PROTECTED]> wrote:
> > > [1,12,-3,14,-6,3,4,-2]
>
> > > Check if your approach works here. Apparently not. A subset of an array
> > > should also be continuous, by definition.
>
> > > On 10/15/07, Muntasir Azam Khan <[EMAIL PROTECTED]> wrote:
>
> > > > On Oct 13, 11:39 pm, kannan <[EMAIL PROTECTED]> wrote:
> > > > > hellow!
> > > > > here is the problem statement.
> > > > > you have to find the subset having the maximum sum in the given
> > array
> > > > > of +ve and -ve numbers.
> > > > > try not to follow brute force method.
>
> > > > I'm not sure if I'm understanding the question correctly, but if you
> > > > are looking for the subset rather than the subsequece with maximum
> > > > sum, just taking the sum of all the positive numbers in the list is
> > > > the answer.
>
> > > > Regards,
> > > > Muntasir- Hide quoted text -
>
> > > - Show quoted text -
>
> > By definition,
> > a subarray/substring of the original sequence is continuous.
>
> > a subsequence is not necessarily continuous but the relative position
> > of the members in the subsequence must be the same as that in the
> > original sequence.
>
> > a subset is need not be continuous or in the same relative order. A
> > subset is simply a set whose members are all taken from the original
> > array. A set is by definition unordered (i.e. {1,2} and {2,1} are
> > considered to be the same set).
> > seehttp://en.wikipedia.org/wiki/Set
>
> > The OP asks for the subset with maximum sum, not the subsequence or
> > the subarray. That is the reason why I said I wasn't sure if I
> > understood the problem, for finding the maximum sum subset is trivial.
> > Perhaps he meant subsequence or subarray?
>
> > Regards,
> > Muntasir- Hide quoted text -
>
> - Show quoted text -
Actually the subsequence with maximum sum can also be found by taking
only positive elements from the array. I think he means contiguous
subarray. Your idea about omitting negative numbers at the beginning
and the end is right, and in fact you can omit negative elements
anywhere in the array and get a subsequence/subset, thus you can
simply omit all negative elements and get a subset and subsequence
with maximum sum.
Regards,
Muntasir
--~--~---------~--~----~------------~-------~--~----~
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.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
