Update appNew update is available. Click here to update.
sidenav-btnClose
Topic list
Mining Diamonds
HARD
9 upvotes
Dynamic Programming
Arrays
Topics (Covered in this problem)
Problem solved
Badge
Skill meter
Dynamic Programming
-
-
Arrays
-
-
Other topics
Problem solved
Badge
Skill meter
Strings
-
-
Matrices (2D Arrays)
-
-
Linked List
-
-
Sorting
-
-
Binary Search
-
-
Stacks & Queues
-
-
Trees
-
-
Graph
-
-
Greedy
-
-
Tries
-
-
SQL
-
-
Binary Search Trees
-
-
Heap
-
-
Bit Manipulation
-
-
Solve problems & track your progress
Checkout your overall progress in every topic here
Become
userLevel
Sensei
in DSA topics
Open the topic and solve more problems associated with it to improve your skills
Check out the skill meter for every topic
See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Mining Diamonds

Contributed by
TanishkTonk
Hard
yellow-spark
0/120
Share
9 upvotes

Problem Statement

There are ‘N’ diamonds in a mine. The size of each diamond is given in the form of integer array ‘A’. If the miner mines a diamond, then he gets 'size of previous unmined diamond * size of currently mined diamond * size of next unmined diamond' number of coins. If there isn’t any next or previous unmined diamond then their size is replaced by 1 while calculating the number of coins.

Vladimir, a dumb miner was assigned the task to mine all diamonds. Since he is dumb he asks for your help to determine the maximum number of coins that he can earn by mining the diamonds in an optimal order.

For example:
Suppose ‘N’ = 3, and ‘A’ = [7, 1, 8]

The optimal order for mining diamonds will be [2, 1, 3].
State of mine -    [7, 1, 8]    [7, 8]    [8]
Coins earned -    (7*1*8) + (1*7*8) + (1*8*1)  = 56 + 56 + 8 = 120
Hence output will be 120.
Detailed explanation ( Input/output format, Notes, Constraints, Images )
Sample Input 1 :
2
3
7 1 8
2
9 1
Sample Output 1 :
120
18
Explanation For Sample Input 1 :
For First Case - Same as explained in above example.

For the second case - 

‘N’ = 2, and ‘A’ = [9, 1]

The optimal order for mining diamonds will be [2, 1].
State of mine -    [9, 1]    [9]
Coins earned -    (1*9*1) + (1*9*1) = 9 + 9 = 18
Hence output will be 18..
Sample Input 2 :
2
5
1 2 3 4 5
4
1 5 2 8
Sample Output 2 :
110
136
Reset Code
Full screen
Auto
copy-code
Console