Maximum Score

Hard
0/120
3 upvotes
Asked in companies
IntuitJio Platforms Limited

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].
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
5 3
1 3 5 7 9
3 5 100
4 3
1 2 3 5
1 3 10
Sample Output 1:
109
16
Explanation of sample input 1:
For the first test case,

The numbers Ninja will be pick are [1,3,5,100].The sum of unique numbers are 109.
Hence, the answer is 109. 

For the second test case:

 The numbers Ninja will be pick are [1,2,3,3,10].The sum of unique numbers are 16(1+2+3+10).
 Hence, the answer is 16.
Sample Input 2:
2
5 4
2 4 5 8 10
4 6 8 9
5 5
1 2 3 4 5
6 7 8 9 10
Sample Output 2:
30
40
Hint

Try calculating the answer for length n, try to find the answer for n-1.

Approaches (2)
Dynamic Programming

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).
Time Complexity

O( N+M ), where ‘N’ is the size of array ‘A’ and ‘M’ is the size of array ‘B’.

 

In this approach, we are traversing both arrays to calculate the values of DP_A and DP_B. So total number of elements traversed is M+N. Hence the overall time complexity is O(M+N).

Space Complexity

O(M+N), where ‘N’ is the size of array ‘A’ and ‘M’ is the size of array ‘B’.

 

In this approach, we are using two arrays ‘DP_A’ and ‘DP_B’ of size ‘N’ and ‘M’ to store the dp table. Hence, the overall space complexity is O(N + M).

Code Solution
(100% EXP penalty)
Maximum Score
Full screen
Console