Maximise Sum
Tag(s):

## Dynamic Programming, Easy-Medium, Two dimensional

Problem
Editorial
Analytics

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:

$1 \le N \le 10^3$

$1 \le A_i \le 10^6$

SAMPLE INPUT
5
1 4 2 3 5
SAMPLE OUTPUT
24

Explanation

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

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

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

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

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

Time Limit: 1,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

September Easy '17

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Dynamic Programming
• Math > Combinatorics
• Algorithms > String Algorithms
• Data Structures > Advanced Data Structures
Уведомления

?