Hi Arunachalam!
Good work! Is there some way you can stop duplicates in the final
answer? i.e; ai+bj can be considered more than once as answer.
Sorry, i am poor at mathematics so can't figure it out how to get its
running time.
But still there is some way that we can get O(n) even in worst
hooo
--~--~-~--~~~---~--~~
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
Hi,
This is a standard MS interview question.
Give an O(n) algorithm to find the subset of an array A[n] with largest
sum.
Anticipating a healthy and useful discussion on this.
Thanks,
Shishir
--~--~-~--~~~---~--~~
You received this message because you are
I dont get it, if its just the subset, then just get the sum of all positive nos. may be you wanted continous nos.another variation of the question can be, find the subset where (sum of subset)/(max element of the set) is maximum.
Lets discuss this as well :)Thanks,VijendraOn 4/5/06, shishir
I think it it max sub-sequence problem which is discussed on this link : http://discuss.fogcreek.com/techinterview/default.asp?cmd=showixPost=3052
On 4/5/06, Vijendra Singh [EMAIL PROTECTED] wrote:
I dont get it, if its just the subset, then just get the sum of all positive nos. may be you
For a binary tree with N nodes, I think it will have n-1 edges. So the
totoal lenght is n-1. Am I right?
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
Yes, am sorry, its infact the continous sub-sequence which I missed
in the question.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
i don't understand, i am pretty new at programming.
--~--~-~--~~~---~--~~
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
Is the solution always x = N-4, y = N-3, z = N-2 ?
Suppose we are looking for x and y to minimize the sum.
Sum = a[i]*x + a[j]*y, where 0 = i = x j = y = N.
It is always bigger than a[i]*x + a[j]*x, because x y and all numbers
are positive.
We have to have a y so when y is the last one, the