A row of n energy cells is arranged left to right; cell i holds a charge value v[i]. You will remove all n cells, one at a time, in an order of your choosing. When you remove a cell, you collect a reward equal to the product of its own charge and the charges of its two current immediate neighbors among the cells still remaining at that moment (the cells that were adjacent to it before any of them were removed may no longer be adjacent once cells between them are gone -- always use whichever cells are currently nearest on each side). If the removed cell has no remaining neighbor on the left (it is the current leftmost remaining cell) or no remaining neighbor on the right, treat the missing neighbor's charge as 1 for that removal. Choose the removal order that maximizes the total reward collected over all n removals, and print that maximum total.
Line 1: an integer n.
Line 2: n space-separated non-negative integers, the charge values v[0] ... v[n-1].
A single integer: the maximum total reward achievable over all removal orders.
Example 1
Input
3 3 1 5
Expected
35
Explanation
Remove the middle cell (value 1) first: reward 3*1*5 = 15. Now 3 and 5 are adjacent. Remove 3 next — its left neighbor is the boundary 1 and its right neighbor is 5 — for 1*3*5 = 15. Finally remove 5: 1*5*1 = 5. Total 15 + 15 + 5 = 35, the best over all six removal orders.
Example 2
Input
1 9
Expected
9
Explanation
With a single cell, its only neighbors are the boundary (value 1) on both sides, so the reward is 1*9*1=9.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →