[algogeeks] Re: Nice question!! (part 2)

Tue, 26 Sep 2006 09:17:07 -0700

**** If the optimal internal containing a[m] contains one
element, it is simply a[m]
 
But here the optimal interval containing a[m] is not a[m] alone.
4 alone gives you 4 * 4 = 16
Including 7, you will get.... (4 + 7) * 4 = 44
Then include 8 ,  (4+7+8) * 4 = 76
Now try including 2,  (2+4+7+8) * 2 = 21*2 = 42 (This is lesser than previous one)
 
So the optimum one including 4 is, is 4+7+8
 
Now appy the same O(n) procedure to both small half arrays...

 
On 9/26/06, GoCooL <[EMAIL PROTECTED]> wrote:

Prunthaban Kanthakumar wrote:
> Hi,
>
> The proposed solution does not talk about multiplication. It talks about the
> sum alone.
> The sum is simply a[m].
> Of course you need to muliply later.But that does not affect the correctness
> of the solution!

For this set:
5
1 2 4 7 8

what would the steps be?

As you mentioned, if initially, the sum is all we care about, then:

a[l..m-1] = 1 + 2 = 3
a[m] = 4
a[m+1..r] = 7 + 8 = 15

Where do we go from here?

- GoCooL



--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---

Reply via email to