http://www.spoj.com/problems/NITT8/
Theres a nlogn solution for this.
Store the (height,position) array as a vector of pairs
Now our aim is to maximize the friend quotient(i,e maximize both terms a and b in the formula given down)
FQ = minimum height of the 2 girls {term a}* absolute diff of the position of the 2 girls{term b}
Sort the vector based on height
After sorting , considering each height element h of the pair (starting from the maximum. i.e is right side) as the candidate for the minimum height .Let its postion be i.
We have to maximize the difference too.(maximize b). So for each position i ( position where our candidate height h is located) find the value that is most maximum than it and store it in max1.also find the value that is most minimum that it and store it in min1.
You will find out that you have to check only the right side of the position i to find the max1 and min1 since if we go left our height value will be reduced.
Calculate the F.Q at each iteration and store the maximum F.Q in a variable and update the variable at each stage.
[gist https://gist.github.com/vishnujayvel/8996647]
coding hangover 