Advertisement
HjHimansh

Baloon Burst - TLE

Aug 1st, 2020
1,789
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. class Solution {
  3.   unordered_map<string, int> memo;
  4. public:
  5.  
  6.   typedef struct {
  7.     int left;
  8.     int itsVal;
  9.     int right;
  10.   } Baloon;
  11.  
  12.   int h_maxCoins(vector<Baloon> &nums) {
  13.    
  14.     string key = "";
  15.     for(auto &x: nums){
  16.       key+= to_string(x.left) + "|" + to_string(x.itsVal) + "|" + to_string(x.right) + "||";
  17.     }
  18.    
  19.     if(memo.count(key)) return memo[key];
  20.    
  21.    
  22.     int answer = 0;
  23.     for(int i=0; i<nums.size(); i++){
  24.      
  25.       if(nums[i].itsVal == -1) continue;
  26.      
  27.       //else we can burst it..
  28.       int tempAns = nums[i].itsVal;
  29.       if(nums[i].left >= 0) tempAns *= nums[nums[i].left].itsVal;  
  30.       if(nums[i].right < nums.size()) tempAns *= nums[nums[i].right].itsVal;
  31.      
  32.        
  33.        
  34.       int temp1 = nums[i].itsVal;
  35.       int temp2, temp3;
  36.       nums[i].right <  nums.size() ? (temp2 = nums[nums[i].right].left) : 0;
  37.       nums[i].left >= 0 ? (temp3 = nums[nums[i].left].right) : 0;
  38.      
  39.       nums[i].itsVal = -1;
  40.       nums[i].right < nums.size() ? (nums[nums[i].right].left = nums[i].left) : 0;
  41.       nums[i].left >= 0 ? (nums[nums[i].left].right = nums[i].right) : 0;
  42.       tempAns += h_maxCoins(nums);
  43.      
  44.       nums[i].itsVal = temp1;
  45.       nums[i].right < nums.size() ? ( nums[nums[i].right].left = temp2 ): 0;
  46.       nums[i].left >= 0 ? (nums[nums[i].left].right = temp3) : 0;
  47.      
  48.       answer = max(answer, tempAns);
  49.     }
  50.     memo[key] = answer;
  51.     return answer;
  52.   }
  53.  
  54.   int maxCoins(vector<int>& copy) {
  55.     vector<Baloon> nums(copy.size());
  56.    
  57.     for(int i=0; i<copy.size(); i++){
  58.       nums[i].left = i-1;;
  59.       nums[i].right = i+1;
  60.       nums[i].itsVal = copy[i];
  61.     }
  62.    
  63.     return h_maxCoins(nums);
  64.   }
  65. };
Advertisement
RAW Paste Data Copied
Advertisement