Maximum Score from Two Arrays | Which Test Case is this approach missing?

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 or B. 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] and K=5
Output: 24

Explanation: An optimal solution is as follows:

• Choose from end of B, add 9 to score. Remove 9 from B
• Choose from start of A, add 3 to score. Remove 3 from A
• Choose from start of B, add 2 to score. Remove 2 from B
• Choose from start of B, add 8 to score. Remove 8 from B
• Choose from end of A, add 2 to score. Remove 2 from A

The total score is 9+3+2+8+2 = 24

---

Constraints

• 1 ≤ N ≤ 6000
• 1 ≤ M ≤ 6000
• 1 ≤ A[i] ≤ 10⁹
• 1 ≤ B[i] ≤ 10⁹
• 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 performed i operations from A
• j indicates that we have performed j operations from B
• Total operation is thus i+j
• AL indicates index on left of which which all integers of A are used. Similarly AR indicates index on right of which all integers of A used for operation.
• BL indicates index on left of which which all integers of B are used. Similarly BR indicates index on right of which all integers of B 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?

---

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 exceeds AR“ or “BL exceeds BR“ 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]