diff options
Diffstat (limited to 'other/max_score_mult_opp.cpp')
-rw-r--r-- | other/max_score_mult_opp.cpp | 31 |
1 files changed, 31 insertions, 0 deletions
diff --git a/other/max_score_mult_opp.cpp b/other/max_score_mult_opp.cpp new file mode 100644 index 0000000..7758a29 --- /dev/null +++ b/other/max_score_mult_opp.cpp @@ -0,0 +1,31 @@ +#include "leetcode.h" + +class Solution { +public: + int maximumScore(vector<int> &nums, vector<int> &multipliers) { + n = nums.size(); + m = multipliers.size(); + memset(memo, -1, sizeof(memo)); + return dp(0, 0, nums, multipliers); + } + +private: + int m, n, memo[1000][1000]; + int dp(int l, int i, vector<int> &nums, vector<int> &multipliers) { + if (i == m) + return 0; + if (memo[l][i] != -1) + return memo[l][i]; + int pickLeft = + dp(l + 1, i + 1, nums, multipliers) + nums[l] * multipliers[i]; + int pickRight = dp(l, i + 1, nums, multipliers) + + nums[n - (i - l) - 1] * multipliers[i]; + return memo[l][i] = max(pickLeft, pickRight); + } +}; + +int main() { + Solution obj; + vector<int> nums = {1, 2, 3}, multipliers = {3, 2, 1}; + cout << obj.maximumScore(nums, multipliers); +} |