0
$\begingroup$

Consider that there are N girls standing in a line..their positions range from 1 to N... and also given is their heights...we need to select two girls such that their friendship quotient is very high...friendship quotient is defined as the product of absolute difference between the position of the two girls and the minimum height of the two girls... for ex..)consider there are 5 girls and their corresponding heights are 3 4 1 6 2...here the girls from position 1 (height 3) and positin 4 (height 6) will be selected since they have the maximum friendship quotient....since absolute diff between their position is 4 - 1 = 3 and the min height among them is ie.)min(6,3) = 3...therefore their friendship quotient = 3 * 3 = 9 which is the maximum of all...

therefore my question is given a set of numbers(height of girls) how can we find the maximum friendship quotient...i want to know whether this problem can be solved using some other efficient method than using the naive method of comparing one girl with the remaining N-1 girls and then arriving at a solution...thanks in advance....

1 Answers 1

0

First, the tallest girl must be involved in the maximal pair. This is because, given any pair, replacing the taller girl with the tallest one cannot decrease the friendship quotient, and unless the replacement actually did nothing, increases it.

Given the height of the tallest girl to be $h$, the other girl's height should be as close to $\frac{h}2$ as possible. This is because, we are trying to maximize $x(h-x) = \frac{h^2}4 - \left(\frac{h}2 -x\right)^2$, where $x$ is the height of the shorter girl.

  • 0
    ronno:thank u...2012-11-01