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

Mon, 25 Sep 2006 07:33:40 -0700

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!
 
Regards,
Prunthaban

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

This is the original thread:

http://groups.google.com/group/algogeeks/browse_frm/thread/b6e605273a09d79d/#

But since that thread has been closed by the manager as a result of
which I'm unable to post to it anymore, I'm creating this new thread.

The original problem states -
"the value of some period of human life is proportional to the sum of
the emotional values of the days in the given period, multiplied by the
smallest emotional value of the day in it."

And in Post# 12 of the above mentioned thread, this is a part of the
solution suggested.

>  * Divide the elements in the middle: a[l..m-1], a[m], a[m+1..r]
>  * Recursively compute the optimal interval entirely in the left half
>  * Recursively compute the optimal interval entirely in the right half
>  * Compute the optimal interval containing a[m]
>  * Return the best of the three intervals

> The key step for efficiency is computing the optimal
> interval containing a[m] in linear time. Here's a greedy solution.

> * If the optimal internal containing a[m] contains one
>   element, it is simply a[m]


So, for this example -

1, 2, 4, 7, 8

a[m] being suggested is 4 when clearly it should be -

a[m] = 4 = 4 * 4 = 16.

Am I missing something from the proposed solution 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 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
-~----------~----~----~----~------~----~------~--~---

Reply via email to