I got this problem on one of my tests. I wrote a Recursive solution for it (I tried it on a few test cases, it seems to be working fine). I am trying to memoize this code, but am not able to do that.
The problem statement goes like this,
You are playing Fantasy Cricket on IPL11 App. The game is a bit different from other Fantasy Cricket Apps.
Here you are given two lists of players. Both lists contain n players each.
The list is denoted based on the value they provide.
You need to select exactly n players out of these 2*n players.
The selection needs to be done based on the following rules.
- You can select either from the end of
list1or end oflist2 - Once you select a player, he is removed from that list.
- To get access to better players, you also have an option to discard a player and remove them from the end of the list. You can do the discard operation at most k times.
Naturally, you would want to get the maximum value possible in your team. Find the maximum value that you can get after selecting n players from the 2 lists based on the above rules.
Example
n: 6
list1: [10, 13, 31, 12, 12, 18]
list2: [34, 12, 3, 23, 11, 13]
k: 2
O/P: 112
Explanation:
* Select 18 (list1)
* Select 13 (list2)
* Skip 11 (list2)
* Select 23 (list2)
* Select 12 (list1)
* Skip 3 (list2)
* Select 12 (list2)
* Select 34 (list2)
My Recursive Solution,
public static int helper(int[] list1, int[] list2, int n1, int n2, int k, int count) {
if(count == n) return 0;
int chooseFromList1 = Integer.MIN_VALUE;
int chooseFromList2 = Integer.MIN_VALUE;
if(n1 > 0) {
chooseFromList1 = list1[n1-1]+helper(list1, list2, n1-1, n2, k, count+1);
}
if(n2 > 0) {
chooseFromList2 = list2[n2-1]+helper(list1, list2, n1, n2-1, k, count+1);
}
int temp = Integer.MIN_VALUE;
if(k > 0) {
int skipList1 = helper(list1, list2, n1-1, n2, k-1, count);
int skipList2 = helper(list1, list2, n1, n2-1, k-1, count);
temp = Math.max(skipList1, skipList2);
}
return Math.max(Math.max(chooseFromList1, chooseFromList2), temp);
}
What I did is, I took 4 choices in this recursive code,
- Take last element from
list1if n1 > 0 - Take last element from
list2if n2 > 0 - Skip last element from
list1if k > 0 - Skip last element from
list2if k > 0
I want to convert it to Top Down DP, but not able to write the code for it.