Amazon SDE off campus OA

Round 1

Questions: Problem statement:
The warehouse head wants to measure the efficiency of the way parcels are shipped. The volume of each parcel is represented in an array parcel. Each day, the first and last parcels in the array are shipped until all of them are dispatched.

The head comes up with metrics to calculate warehouse efficiency. Each day before shipping, any parcel in the warehouse is chosen, and its volume is added to the sum of total efficiency. A parcel can only be chosen once.

Given the array parcel, find the maximum possible efficiency of the warehouse.

Constraints:
1 <= T <= 10^5
1 <= n <= 10^5
0 <= parcel[i] <= 10^9
The sum of n over all test cases doesn't exceed 10^5

Sample Input:
4
4
1 5 5 2
6
4 4 8 5 3 2
7
2 1 8 5 6 2 4
3
2 0 3

Sample Output:
10
17
23
3

Explanation:
In the first example, the optimal way is to select the parcel volumes as follows: 5(index 1) + 5(index 2) = 10
In the second example, the optimal order is to select parcels: 4(index 0) + 5(index 3) + 8(index 2) = 17
In the third example, the optimal order is to select parcels: 4(index 6) + 6(index 4) + 8(index 2) + 5(index 3) = 23

Specific question not provided.