Two integer arrays, nums and multipliers, of sizes n and m, respectively, are provided to you, where n >= m. The arrays are all one-dimensional.
You start with a score of zero. You need to carry out precisely m operations. On the ith (1-indexed) action, you will:
Choose one integer x from the beginning or end of the array nums.
Increase your score by multipliers[i] * x.
Take x out of the array nums.
After doing m operations, return the highest possible score.
Example 1:
Input: nums = [1,2,3], multipliers = [3,2,1] Output: 14 Explanation: An optimal solution is as follows: - Choose from the end, [1,2,3], adding 3 * 3 = 9 to the score. - Choose from the end, [1,2], adding 2 * 2 = 4 to the score. - Choose from the end, [1], adding 1 * 1 = 1 to the score. The total score is 9 + 4 + 1 = 14.
Example 2:
Input: nums = [-5,-3,-3,-2,7,1], multipliers = [-10,-5,3,4,6] Output: 102 Explanation: An optimal solution is as follows: - Choose from the start, [-5,-3,-3,-2,7,1], adding -5 * -10 = 50 to the score. - Choose from the start, [-3,-3,-2,7,1], adding -3 * -5 = 15 to the score. - Choose from the start, [-3,-2,7,1], adding -3 * 3 = -9 to the score. - Choose from the end, [-2,7,1], adding 1 * 4 = 4 to the score. - Choose from the end, [-2,7], adding 7 * 6 = 42 to the score. The total score is 50 + 15 - 9 + 4 + 42 = 102.
Solution :
Python :
DP solution :
dp = [0] * (len(mul) + 1)
for m in range(len(mul) - 1, -1, -1):
pd = [0] * (m + 1)
for l in range(m, -1, -1):
pd[l] = max(dp[l + 1] + mul[m] * nums[l],
dp[l] + mul[m] * nums[~(m - l)])
dp = pd
return dp[0]
CPP
DP Solution :
- Instead of initializing DP by 0, initialize it by
INT_MIN
. - Why ? Because 0 is a valid score.
- As 0 is a valid score, when the
dp[j][i]
is indeed 0, we will recompute the value and thus waste time. We can initializedp[j][i]
to INT_MIN instead.
class Solution {
public:
vector<vector<int>> dp;
int solve(int i, int n, int j, vector<int> &nums, vector<int> &M){
if (j == M.size()) return 0;
if (dp[i][j] != INT_MIN) return dp[i][j];
// Left Side
int left = solve(i + 1, n, j + 1, nums, M) + (nums[i] * M[j]);
// Right Side
int right = solve(i, n, j + 1, nums, M) + (nums[(n - 1) - (j - i)] * M[j]);
return dp[i][j] = max(left, right);
}
int maximumScore(vector<int>& nums, vector<int>& M) {
int n = nums.size(), m = M.size();
dp.resize(m + 1, vector<int>(m + 1, INT_MIN));
return solve(0, n, 0, nums, M);
}
};
Java
class Solution {
int N, M;
public int maximumScore(int[] nums, int[] multipliers) {
N = nums.length;
M = multipliers.length;
return helper(nums, multipliers, 0, 0, new Integer[M][M]);
}
private int helper(int[] nums, int[] multipliers, int left, int index, Integer[][] dp) {
int right = N - 1 - (index - left);
if (index == M) return 0;
if (dp[left][index] != null) return dp[left][index];
int res = Math.max(
nums[left] * multipliers[index] + helper(nums, multipliers, left+1, index+1, dp),
nums[right] * multipliers[index] + helper(nums, multipliers, left, index+1, dp));
dp[left][index] = res;
return res;
}
}
what does dp mean?
Dynamic Programming
I visted many webssites except thhe audio quality for audio songs existin at this website
iss actually wonderful.
Have yyou ever tought abvout adding a lttle bit more than jst yourr articles?
I mean, what youu ssay iis important andd everything. Nevertheless jhst imagine if yoou added some great visuals or
vdeo clips to ive yoiur posts more, “pop”! Youur contgent iss excellent butt wifh pihs and
videos, thbis ssite could certaionly be one of the
est inn itts niche. Suplerb blog!
Doees your website have a conact page? I’m having probleems
locating it but, I’d lioke too suoot yyou an e-mail.
I’ve goot somme sugghestions for your blokg you mijght bbe intereted iin hearing.
Eituer way, grest webite and I lok forward to seeing itt expand ovver time.
bookmarked!!, I like your web site!