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).
> see http://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
>
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
