Make The Array Empty

Problem Description

Given an integer array A, you have to perform certain operation any number of times on the array A.

In each operation you can remove any one of the three valid pairs:

Remove First, and the Last element of the array and cost of this operation will be LCM(firstElement, LastElement)
Remove First, and Middle element of the array and cost of this operation will be LCM(firstElement, middleElement)
Remove Middle, and the Last element of the array and cost of this operation will be LCM(middleElement, LastElement)

You have to find the maximum total cost it will take to make the array A empty.

NOTE:

In even-sized array, there are two middle elements, so always consider the second middle element as the middle element of the array.

Problem Constraints

1 <= |A| <= 20

Length of array A is always even.

1 <= A[i] <= 10³

Input Format

First argument is an integer array A.

Output Format

Return a single integer denoting the maximum total cost it will take to make the array A empty.

Example Input

Input 1:

 A = [1, 2, 3, 4]

Input 2:

 A = [2, 4, 8 ,6]

Example Output

Output 1:

Output 2:

Example Explanation

Explanation 1:

 In first operation remove 3 and 4 from the array A which will cost = lcm(3, 4) = 12
 So now A = [1, 2]
 In second operation remove 1 and 2 from the array A which will cost = lcm(1, 2) = 2

Total Cost  = 2 + 12 = 14

Explanation 2:

 In first operation remove middle and the last element i.e 8 and 6 from the array A which will cost = lcm(8, 6) = 24
 In Second operation remove 2 and 4 which will cost us 4.

Total Cost = 4 + 24 = 28

NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a question? Checkout Sample Codes for more details.

Start solving Make The Array Empty on Interview Code Editor

Hints

Hint 1
Solution Approach
Complete Solution

Make The Array Empty

Discussion