NITT8 - Dating Rishi

no tags 

                                                                      Dating Rishi

                Its been Monday and Rishi   Dude is planning to select a girl to date for this week. So all N girls are standing in a line  from 1 to N so that Rishi will select one of them.  The girls are standing in a straight line but randomly. They know they cannot predict what Rishi The Great likes, He may like hot,smart,tall,short,witty,white,black or anything . But wait , Rishi ,the Coolest Dude  plans to date two girls this week !!!  How lucky they are ????  . But he wants to select two girls whose friendship quotient is maximum so that they wont fight too much over  Rishi during the date. He is shy too ! .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.

                Can you help Rishi to find the maximum friendship quotient ?

Input Specification:

 

 The first line of input file contains T which denotes number of testcases.2*T lines follows.

First line of each test case contains an integer N .

Second line of each test case contains N space seperated integers denoting the height of each girl.

 

Output Specification:

 

The output must contain T lines each line corresponding to a testcase.

Constraints:

T<=20

N<=100000

Height[i]<=10^9

Sample Input:

2

4

3 2 1 3

5

4 2 3 1 4

Sample Output:

9

16


hide comments
deerishi: 2016-10-16 07:21:22

From a guy who goes by the name Rishi , its an awesome problem! lol!!

ashish22_dwd: 2015-07-08 19:37:31

nice problem.. solved in O(n) time. AC in 0.02s

Last edit: 2016-10-18 22:18:25
Akshat Mathur: 2015-06-17 14:43:59

Really nice problem.....learnt a lot !!

sobriquet: 2014-09-20 12:59:30

Awesome problem. Mind long long instead int.

||N0VICE||: 2014-08-23 17:16:33

150th AC :)
AC at first attempt

Last edit: 2014-08-23 17:22:45
AKASH GOEL: 2014-08-23 14:24:32

gud one

AAKASH TYAGI: 2014-08-09 22:08:21

a very good problem
keep thinking o(nlogn) solution will definitely strike

Archit Jain: 2014-08-09 16:08:02

finally ac after a long time
use long long int those getting wa

Last edit: 2014-08-09 16:11:40
TAUSHIF ALI: 2014-07-14 21:48:20

nic one :)

Agam Gupta: 2014-05-30 12:46:21

gud one !!


Added by:jack(chakradarraju)
Date:2012-09-30
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Radhakrishnan