Problem Statement
Given two integer arrays A
and B
of size N
and M
respectively. You begin with a score of 0
. You want to perform exactly K
operations. On the iᵗʰ
operation (1-indexed), you will:
- Choose one integer
x
from either the start or the end of any one array,A
orB
. Remove it from that array - Add
x
to score.
Return the maximum score after performing K
operations.
Example
Input:
A = [3,1,2]
,B = [2,8,1,9]
andK=5
Output:24
Explanation: An optimal solution is as follows:
- Choose from end of
B
, add 9 to score. Remove 9 fromB
- Choose from start of
A
, add 3 to score. Remove 3 fromA
- Choose from start of
B
, add 2 to score. Remove 2 fromB
- Choose from start of
B
, add 8 to score. Remove 8 fromB
- Choose from end of
A
, add 2 to score. Remove 2 fromA
The total score is
9+3+2+8+2 = 24
Constraints
- 1 ≤
N
≤ 6000 - 1 ≤
M
≤ 6000 - 1 ≤
A[i]
≤ 109 - 1 ≤
B[i]
≤ 109 - 1 ≤
K
≤N
+M
My Approach
Since, greedy [choosing maximum end from both array] approach is failing here [because it will produce conflict when maximum end of both array is same], it suggests we have to look for all possible combinations. There will be overlapping sub-problems, hence DP!
Here is the python
reprex code for the same.
A = [3,1,2] N = len(A) B = [2,8,1,9] M = len(B) K = 5 memo = {} def solve(i,j, AL, BL): if (i,j,AL,BL) in memo: return memo[(i,j,AL,BL)] AR = (N-1)-(i-AL) BR = (M-1)-(j-BL) if AL>AR or BL>BR or i+j==K: return 0 op1 = A[AL] + solve(i+1,j,AL+1,BL) op2 = B[BL] + solve(i,j+1,AL,BL+1) op3 = A[AR] + solve(i+1,j,AL,BL) op4 = B[BR] + solve(i,j+1,AL,BL) memo[(i,j,AL,BL)] = max(op1,op2,op3,op4) return memo[(i,j,AL,BL)] print(solve(0,0,0,0))
In brief,
i
indicates that we have performedi
operations fromA
j
indicates that we have performedj
operations fromB
- Total operation is thus
i+j
AL
indicates index on left of which which all integers ofA
are used. SimilarlyAR
indicates index on right of which all integers ofA
used for operation.BL
indicates index on left of which which all integers ofB
are used. SimilarlyBR
indicates index on right of which all integers ofB
used for operation.
We are trying out all possible combination, and choosing maximum from them in each step. Also memoizing our answer.
Doubt
The code worked fine for several test cases, but also failed for few. The message was Wrong Answer means there was no Time Limit Exceed, Memory Limit Exceed, Syntax Error or Run Time Error. This means there is some logical error only.
Can anyone help in identifying those Test Cases? And, also in understanding intuition/reason behind why this approach failed in some case?
Advertisement
Answer
The approach is failing because the Recursive Functions stops computing further sub-problems when either “AL
exceeds AR
“ or “BL
exceeds BR
“.
We should stop computing and
return 0
only when both of them are True. If either of “AL
exceedsAR
“ or “BL
exceedsBR
“ evaluates to False, means we can solve that sub-problem.
Moreover, one quick optimization here is that when N+M==K
, in this case we can get maximum score by choosing all elements from both the arrays.
Here is the correct code!
A = [3,1,2] B = [2,8,1,9] K = 5 N, M = len(A), len(B) memo = {} def solve(i,j, AL, BL): if (i,j,AL,BL) in memo: return memo[(i,j,AL,BL)] AR = (N-1)-(i-AL) BR = (M-1)-(j-BL) if i+j==K or (AL>AR and BL>BR): return 0 ans = -float('inf') if AL<=AR: ans = max(A[AL]+solve(i+1,j,AL+1,BL),A[AR]+solve(i+1,j,AL,BL),ans) if BL<=BR: ans = max(B[BL]+solve(i,j+1,AL,BL+1),B[BR]+solve(i,j+1,AL,BL),ans) memo[(i,j,AL,BL)] = ans return memo[(i,j,AL,BL)] if N+M==K: print(sum(A)+sum(B)) else: print(solve(0,0,0,0))
[This answer was published taking help from DarryIG‘s Answer. The reason for publishing answer is to write code similar to code in question body. DarryIG‘s answer used different prototype for function]