| 12 | class Solution { |
| 13 | public: |
| 14 | int maxCoins(vector<int>& nums) { |
| 15 | vector<int> num (nums.size() + 2, 0); |
| 16 | int n = 1; |
| 17 | for (int i: nums) if (i > 0) num[n++] = i; |
| 18 | num[0] = num[n++] = 1; |
| 19 | |
| 20 | vector<vector<int>> dp (nums.size() + 2, vector<int> (nums.size() + 2, 0)); |
| 21 | for (int k=2; k<n; k++) { |
| 22 | // k is the range length |
| 23 | for (int left = 0; left < n - k; ++ left) { |
| 24 | int right = left + k; |
| 25 | for (int i = left + 1; i < right; i++) { |
| 26 | dp[left][right] = max(dp[left][right], |
| 27 | num[left] * num[i] * num[right] + dp[left][i] + dp[i][right]); |
| 28 | } |
| 29 | } |
| 30 | } |
| 31 | return dp[0][n-1]; |
| 32 | } |
| 33 | }; |
| 34 | |
| 35 | int main() { |
nothing calls this directly
no outgoing calls
no test coverage detected