Unique Element Problem :
Difficulty Level : Hard
Submissions : 405
Asked In :
Marks :10
: 6 | : 1
You are given an array of size $$$N$$$. The power of the array represents the sum of the values that you obtain after performing the described operations for N times.
Your task is to delete the array by performing the following operations:
• For any $$$turn_i$$$ where $$$(1 \le i \le N)$$$, delete either of the end (first or last) elements of the remaining array.
• Before deleting that element (let's say at index $$$K$$$), it contributes to the sum of the values as $$$Arr[K]*turn_i + SV_i$$$ the power of the array. Here, $$$turn_i$$$ represents the number of turns in which you are performing the operation.
• $$$SV_i$$$ represents the value of the maximum element that is present in the remaining array before the $$$i^{th}$$$ turn is performed.
You are required to perform this in such a way that you maximize the value of the power of the array.
The input consists of multiple test cases. The first line contains a single integer t $$$(1 \le t \le 10)$$$ — the number of test cases. The description of the test cases follows.
The first line contains the integer $$$N$$$, $$$(1 \le N \le 10^3)$$$ denoting the size of the array.
The second line consists of $$$N$$$ integers, $$$(a_1,a_2,...a_N)$$$ $$$(1 \le a_i \le 10^9)$$$ denoting the elements of the array.
For each test case in a new line, print the value representing the maximum power that can be obtained after the array is completely deleted.
1 5 5 4 3 6 2
96
