# 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.
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.
49.     }
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. };