Maximise Sum

4.6

13 votes
Dynamic Programming, Easy, Two dimensional
Problem

Given an array A of N numbers, and an initially empty array P, you can do operations of 4 types on it:

  1. Take the last number of array A, remove it and add it to P.
  2. Take the last two numbers of array A (if size of array is greater than 1), remove them and add their product to P.
  3. Reverse array A, take the last number of array A, remove it and add it to P.
  4. Reverse array A, take the last two numbers of array A (if size of array is greater than 1), remove them and add their product to P.

Note that after each operation, array A becomes smaller and maybe reversed. You need to continue adding elements to array P until the array A has 0 elements. You need to maximise the sum of all the values in array P.

Input:

First line contains a single integer N. Next line contains N space separated integers denoting the array A.

Output:

Output the maximum sum of all elements of array P that can be obtained by doing the 4 operations as described above on the array A.

Constraints:

1N103

1Ai106

Sample Input
5
1 4 2 3 5
Sample Output
24
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

We can get 24 by doing the operations in this order: [2,3,2].

After first operation (2nd) : A=[1,4,2],P=[15]

After second operation (3rd) : A=[2,4],P=[15,1]

After third operation (2nd) : A=[],P=[15,1,8]

Total sum at the end is 15+1+8=24.

Editor Image

?