On Oct 17, 7:37 pm, "Channa Bankapur" <[EMAIL PROTECTED]>
wrote:
> 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
Yes, I misread your post. Your idea is correct. We have been saying
the same things in different ways.
My solution is as follows:
int max_sum(int* array, int size)
{
int sum=0, i;
for (i=0;i<size;i++) if (array[i]>0) sum+=array[i];
return sum;
}
Complexity: O(n)
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
-~----------~----~----~----~------~----~------~--~---
