Muntasir, I think I couldn't convey my point to you. When I said terminal
numbers of the subsequence, i didn't mean for the whole array. Lets try to
solve the problem starting with a brute-force algo.
BruteForce:
Let array be a[0..n-1]
sum = 0
for i = 0 to n-1
sumPass = 0
sumCumu = 0
for j = i to n-1
sumCumu += a[j]
if (sumCumu > sumPass) then sumPass = sumCumu
endfor
if (sumPass > sum) then sum = sumPass
endfor
print sum
Let me apply the constraint i was talking about and improve the preformance
to some extent.
Improved1:
Let array be a[0..n-1]
sum = 0
for i = 0 to n-1
if (a[i] < 0) continue with next pass
sumPass = 0
sumCumu = 0
for j = i to n-1
sumCumu += a[j]
if (sumCumu > sumPass) sumPass = sumCumu
endfor
if (sumPass > sum) sum = sumPass
endfor
print sum
Complexity of Brute-Force is O(n*n)
Complexity of Improved1 is O(m*n) where is m is the number of positive
entries in the list and m <= n
Going forward, I've one more improvement over the first improvement.
Constraint2: If a positive entry is just next to the subsequence, it must
included in the subsequence. Proof is -- it is only going to increase the
sum. To take advantage of this, we can club consecutive positive entries
into a single logical entry, and similarly sonsecutive negative entries into
a single negative entry. For example, if the sequence is
3, -5, -2, 23, 32, 7, -4, -3, 10, -20
Then the new logical list would be
3, -7, 62, -7, 10, -20
Now apply the Improvement1 algo and you'll get a sum of 65. Talking about
complexity of this method little complex, so i would leave it till it
becomes necessary to talk about.
Regards,
Channa
On 10/17/07, Muntasir Azam Khan <[EMAIL PROTECTED]> wrote:
>
>
>
>
> 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
-~----------~----~----~----~------~----~------~--~---
