# 321. Create Maximum Number

Difficulty: Hard

Frequency: N/A

Given two arrays of length `m` and `n` with digits `0-9` representing two numbers. Create the maximum number of length `k <= m + n` from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the `k` digits. You should try to optimize your time and space complexity.

Example 1:

nums1 = `[3, 4, 6, 5]`
nums2 = `[9, 1, 2, 5, 8, 3]`
k = `5`
return `[9, 8, 6, 5, 3]`

Example 2:

nums1 = `[6, 7]`
nums2 = `[6, 0, 4]`
k = `5`
return `[6, 7, 6, 0, 4]`

Example 3:

nums1 = `[3, 9]`
nums2 = `[8, 9]`
k = `3`
return `[9, 8, 9]`

Test Cases:

Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
```class Solution {
public:
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
int n = nums1.size(), m = nums2.size();
vector<int> result;
for (int i = max(0, k - m); i <= k && i <= n; i++) {
vector<int> tmp = merge(maxArray(nums1, i), maxArray(nums2, k - i), k);
if (greater(tmp, 0, result, 0)) result = tmp;
}
return result;
}
vector<int> merge(vector<int> nums1, vector<int> nums2, int k) {
vector<int> result;
for (int i = 0, j = 0, r = 0; r < k; r++) {
if (greater(nums1, i, nums2, j)) result.push_back(nums1[i++]);
else result.push_back(nums2[j++]);
}
return result;
}
bool greater(vector<int> nums1, int i, vector<int> nums2, int j) {
while (i < nums1.size() && j < nums2.size() && nums1[i] == nums2[j]) {
i++;
j++;
}
return j == nums2.size() || i < nums1.size() && nums1[i] > nums2[j];
}
vector<int> maxArray(vector<int> nums, int k) {
int n = nums.size();
vector<int> result(k, 0);
for (int i = 0, j = 0; i < n; i++) {
while (n - i + j > k && j > 0 && result[j - 1] < nums[i]) j--;
if (j < k) result[j++] = nums[i];
}
return result;
}
};
```

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Submission errors:

Things to learn:

# 312. Burst Balloons

Difficulty: Hard

Frequency: N/A

Given `n` balloons, indexed from `0` to `n-1`. Each balloon is painted with a number on it represented by array `nums`. You are asked to burst all the balloons. If the you burst balloon `i` you will get `nums[left] * nums[i] * nums[right]` coins. Here `left` and `right` are adjacent indices of `i`. After the burst, the `left` and `right` then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:
(1) You may imagine `nums[-1] = nums[n] = 1`. They are not real therefore you can not burst them.
(2) 0 ≤ `n` ≤ 500, 0 ≤ `nums[i]` ≤ 100

Example:

Given `[3, 1, 5, 8]`

Return `167`

```    nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167```

Test Cases:

Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
```class Solution {
public:
int maxCoins(vector<int>& nums) {
vector<int> nums2(nums.size() + 2, 0);
int n = 1;
for (int num : nums) {
if (num > 0) nums2[n++] = num;
}
nums2[0] = nums2[n++] = 1;

vector<vector<int>> dp(n, vector<int>(n, 0));
for (int k = 2; k < n; k++) {
for (int left = 0; left < n - k; left++) {
int right = left + k;
for (int i = left + 1; i < right; i++) {
dp[left][right] = max(dp[left][right], nums2[left] * nums2[i] * nums2[right] + dp[left][i] + dp[i][right]);
}
}
}
return dp[0][n - 1];
}
};
```

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Submission errors:

Things to learn: