Last Updated: 4 Mar, 2022
Mining Diamonds
Hard
Asked in company
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.
Input Format:
The first line of the input contains a single integer ‘T’ representing the no. of test cases.
The first line of each test case contains a single integer value, ‘N’, denoting the number of diamonds in the mine.
The second line of each test case contains ‘N’ space-separated integers, denoting the size of the diamonds in the mine.
Output Format:
For each test case, print a single integer value denoting the maximum number of coins that can be earned by mining the diamonds in an optimal order.
Print a separate line for each test case.
Note:
You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.
Constraints:
1 ≤ T ≤ 100
1 ≤ N ≤ 100
0 ≤ A[i] ≤ 100
1 ≤ ΣN ≤ 300
Time limit: 1 Sec
Approaches
We can recursively iterate over all the possible ways to mine diamonds. We can create a recursive function that returns the maximum coins earned for a subarray. We can recursively calculate the answer for all the subarrays from which we can construct the current subarray. Out of all the possible ways to mine the current subarray we will choose the one in which the number of coins is maximized. Implementation details are as per the following algorithm.
Algorithm:
maxCoinsRec
Function arguments - integer array ‘A’ containing the size of all the diamonds, the starting index ‘i’ of the current subarray, the ending index ‘j’ of the current subarray.
Returns - Maximum number of coins that can be obtained by mining the current subarray.
- If j < i
- Return 0
- If j == i
- Return a[i-1] * a[i] * a[i+1]
- Declare and initialize integer ans = 0
- Iterate over k from i to j which can be chosen as last mined diamond of subarray i,i+1,...j
- ans = max(ans, maxCoinsRec(a, i, k-1) + maxCoinsRec(a, k+1, j) + a[i-1] * a[k] * a[j+1])
- Return ans
Given Function(a)
- Insert 1 in front and back of a
- Declare and initialize n = size of modified a
- Return maxCoinsRec(a, 1, n-2)
We are doing a lot of duplicate calls to the recursive function and calculating the same thing multiple times. We can eliminate this by using a table that contains answers for all the previous calls to the function. We will just return the value saved in the lookup table if we have already solved it for a particular subarray. Implementation details are as per the following algorithm.
Algorithm:
maxCoinsRec
Function arguments - integer array ‘A’ containing the size of all the diamonds, lookup ‘table’ for storing data of already solved subproblems, the starting index ‘i’ of the current subarray, the ending index ‘j’ of the current subarray.
Returns - Maximum number of coins that can be obtained by mining the current subarray.
- If j < i
- Return 0
- If j == i
- Return a[i-1] * a[i] * a[i+1]
- If table[i][j] >= 0
- Return table[i][j]
- Declare and initialize integer ans = 0
- Iterate over k from i to j which can be chosen as last mined diamond of subarray i,i+1,...j
- ans = max(ans, maxCoinsRec(a, table, i, k-1) + maxCoinsRec(a, table, k+1, j) + a[i-1] * a[k] * a[j+1])
- Set table[i][j] = ans
- Return ans
Given Function(A)
- Insert 1 in front and back of A
- Declare and initialize n = size of modified A
- Declare 2D lookup table of size n * n initialized with -1.
- Return maxCoinsRec(a, table, 1, n-2)
We are doing a lot of duplicate calls to the recursive function and calculating the same thing multiple times. We can eliminate this by using an iterative Dynamic Programming approach.
We will iterate on all the subarrays in increasing order of their lengths and store the maximum coins for each subarray which will be used to calculate maximum coins for bigger subarrays. Implementation details are as per the following algorithm.
Algorithm:
The steps are as follows:
- Insert 1 in front and back of A.
- Declare and initialize integer n = size of modified A
- Declare 2D DP array of size n * n
- Iterate over len from 1 to n-2
- Iterate over i from 1 to n-len-1
- Declare and initialize integer j = i+len-1
- Iterate over k from i to j
- dp[i][j] = max(dp[i][j], dp[i][k-1] + dp[k+1][j] + a[i-1] * a[k] * a[j+1])
- Iterate over i from 1 to n-len-1
- Return dp[1][n-2]
Similar problems