maximum-subsequence-score.dart (1844B)
1 //Given two lists find the maximum subsequence where the subsequence length is 2 //k, and the subsequence value is all values from the nums1 list added together 3 //multiplied by the lowest value in the nums2 list. 4 //My code tries all permutations and uses DP/Memoization 5 //to remember all tried permutations to not repeat itself. This 6 //solution is quite slow and gives a TLE. 7 8 class Solution { 9 Map<String, int> memo = {}; 10 int maxScore(List<int> nums1, List<int> nums2, int k) { 11 return max(nums1,nums2,[[], []] , k); 12 } 13 14 int max(List<int> nums1 , List<int> nums2 , List<List<int>> current_nums , int k){ 15 String curr_str = ""; 16 current_nums[0].sort(); 17 current_nums[1].sort(); 18 for(int i = 0 ; i < current_nums[0].length ; ++i){ 19 curr_str += current_nums[0][i].toString() + " " + current_nums[1][i].toString(); 20 } 21 if(memo.containsKey(curr_str)){ 22 return (memo[curr_str] ?? 0); 23 } 24 int current_val = 0; 25 if(k == 0){ 26 int lowest = current_nums[1][0]; 27 for(int i = 0 ; i < current_nums[0].length ; ++i){ 28 current_val += current_nums[0][i]; 29 } 30 current_val = current_val * lowest; 31 } 32 else{ 33 for(int i = 0 ; i < nums1.length ; ++i){ 34 List<int> new_nums1 = List.from(nums1); 35 List<int> new_nums2 = List.from(nums2); 36 int current1 = new_nums1[i]; 37 int current2 = new_nums2[i]; 38 new_nums1.removeAt(i); 39 new_nums2.removeAt(i); 40 List<List<int>> new_nums_list = [List.from(current_nums[0]), List.from(current_nums[1])]; 41 new_nums_list[0].add(current1); 42 new_nums_list[1].add(current2); 43 int curr = max(new_nums1 , new_nums2, new_nums_list , k - 1); 44 if(curr > current_val){ 45 current_val = curr; 46 } 47 } 48 } 49 memo[curr_str] = current_val; 50 return current_val; 51 } 52 }