-->

2/6/21

Maximise Function codechef February 2021 long challenge editorial

 Maximize Function codechef February 2021  long challenge editorial -


Problem Statement- 

You are given a sequence A1,A2,,AN. Find the maximum value of the expression |AxAy|+|AyAz|+|AzAx| over all triples of pairwise distinct valid indices (x,y,z).

Input

  • The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
  • The first line of each test case contains a single integer N.
  • The second line contains N space-separated integers A1,A2,,AN.

Output

For each test case, print a single line containing one integer ― the maximum value of |AxAy|+|AyAz|+|AzAx|.

Constraints

  • 1T5
  • 3N105
  • |Ai|109 for each valid i

Subtasks

Subtask #1 (30 points): N500

Subtask #2 (70 points): original constraints

Example Input

3
3
2 7 5
3
3 3 3
5
2 2 2 2 5

Example Output

10
0
6

Explanation

Example case 1: The value of the expression is always 10. For example, let x=1y=2 and z=3, then it is |27|+|75|+|52|=5+2+3=10.

Example case 2: Since all values in the sequence are the same, the value of the expression is always 0.

Example case 3: One optimal solution is x=1y=2 and z=5, which gives |22|+|25|+|52|=0+3+3=6.

Solution-

Hint - Sort the array.

Solution will be posted anytime soon stay connect .

Must join Telegram channel -https://t.me/competitiveProgrammingDiscussion





Advertiser

all right reserved @technicalkeeda.in. Powered by Blogger.