Last Updated: 18 Oct, 2021

Maximum Score

Hard

Asked in companies

Solve now

Problem statement

Ninja is playing a board game in which two lists of distinct numbers ‘A’ and ‘B’ arranged in a non-descending order are given. The game has certain rules and the player has to pick some numbers from the given list and the score is the sum of unique picked numbers. The rules are:

1.  Choose any list ‘A’ or ‘B’.
2.  Traverse from left to right.
3.  After picking a number, if the picked number is present in both the arrays, you are allowed to traverse to the other array.

You are given arrays,’A’ and ‘B’ of size ‘N’ and ‘M’ respectively. Your task is to find the maximum score Ninja can achieve.

Since the answer can be very large, print answer % (10^9 + 7).

For Example

If the given array are ‘A’ = [1,3,5,7,9] and  ‘B’ = [3,5,100]”.The maximum score can be achieved is 109[1+3+5+100].

Input Format:

The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains two integers, 'N’ and ‘M’, denoting the lengths of the arrays.

The second line contains ‘A’ array.

The third line contains ‘B’ array.

Output Format:

For each test case, print an integer corresponding to the maximum score  % (10^9 +7).  

Print the output of each test case in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N,M <= 10^4.
1 <= A[i], B[i] <= 10^6.  

Time limit: 1 sec

Solve now

Approaches

01 Approach

In this approach, we will create two dp arrays ‘DP_A’ and ‘DP_B’ to calculate the final answer. ’DP_A’[i] represents the maximum answer if we start from any array and finishes at index i-1 of array ‘A’.Similarly, DP_B[j] represents the maximum answer if we start from any array and finish at index i-1 of array ‘B’.

We will calculate the dp table using these conditions:

'DP_A'[i] = 'DP_B'[j] = max('DP_A'[i-1], 'DP_B'[j-1]) + 'A'[i-1] with 'A'[i-1] = 'B'[j-1]

'DP_A'[i] = 'DP_A'[i-1] + 'A'[i-1] with 'A'[i] < 'B'[j]

'DP_B'[j] = 'DP_B'[j-1] + 'B'[j-1] with 'B'[j] < 'A'[i]

At the end we will return the maximum of ‘DP_A’[n] and ‘DP_B’[m].

Algorithm:

Declare two dp tables ‘DP_A’ and ‘DP_B’ of size ‘N+1’ and ‘M+1’ respectively.
Declare two indices i and j.
Set ‘DP_A’[0] as 0.
Set ‘DP_B’[0] as 0.
Set both i and j as 1.
While i is less than ‘N’+1 or j is less than ‘M’+1, do the following:
- If i <= ’N’ and j <= ‘M’ and A[i-1] is equal to B[j-1]:
  - Set DP_A[i] as maximum of ( ‘DP_A’[i-1] ,’DP_B’[j-1] ) + A[i-1].
  - Set DP_B[j] as maximum of ( ‘DP_A’[i-1] ,’DP_B’[j-1] ) + A[i-1].
  - Set i as i+1.
  - Set j as j+1.
  - Continue.
- If i<=’N’ and ( ( j<=’M’ and A[i-1] < B[j-1] ) or (j==M+1) ):
  - Set ‘DP_A[i]’ as ‘DP_A’[i-1] + ‘A[i-1]’.
  - Set i as i+1.
  - Continue.
- Else:
  - Set ‘DP_B[j]’ as ‘DP_B’[j-1] + ‘B[j-1]’.
  - Set j as j+1.
All values of dp table have been calculated.
Set ‘ANS’ as the maximum of ‘DP_A’[‘N’] and ‘DP_B’[‘M’].
Return ‘ANS’ % (10^9 + 7).

Solve now

02 Approach

The main intuition of the solution is that we must take the common elements and won't miss them.And there will be two path between the common elements,and we will take and only take one path with the greater sum.

In this approach, we will iterate through the lists using two pointers ‘i’ and ‘j’ for ‘A’ and ‘B’ array respectively. We will iterate both the arrays always take the step in the smaller element and if we encounter the condition where A[i] is equal to B[j], we have the choice to change our path, we will compare the accumulated sum and pick the greater one.

Algorithm:

Define two integers ‘SUM_A’ and ‘SUM_B’ to store the accumulated sum.
Set ‘SUM_A’ and ‘SUM_B’ as 0.
Set i and j as 0.
Set ‘ANS’ as 0 to store the final answer.
While i < ‘N’ and j < ‘M’,do the following:
- If A[i] < B[j] :
  - Set ‘SUM_A’ as ‘SUM_A’ + A[i].
  - Set i as i+1.
  - Continue.
- If A[i] > B[j]
  - Set ‘SUM_B’ as ‘SUM_B’ + B[j]
  - Set j as j+1.
  - Continue.
- If A[i] == B[j]:
  - Set ‘ANS’ as ‘ANS’ + maximum of ‘SUM_A’ and ‘SUM_B’.
  - Set ‘ANS’ as ‘ANS’ + A[i].
  - Reset both sum values.
  - Set ‘SUM_A’ and ‘SUM_B’ as 0.
  - Set i as i+1.
  - Set j as j+1.
If all elements are not traversed, traverse them.
While i < ’N’:
- Set ‘SUM_A’ as ‘SUM_A’ + A[i].
- Set i as i+1.
While j <’M’:
- Set ‘SUM_B’ as ‘SUM_B’ + B[j].
- Set j as j+1.
Set ‘ANS’ as ‘ANS’ + maximum of ‘SUM_A’ and ‘SUM_B’.
Set ‘ANS’ as ANS%(10^9 + 7).
Return ‘ANS’.

Solve now