You are given two integer arrays nums
and multipliers
of size n
and m
respectively, where n >= m
. The arrays are 1-indexed.
You begin with a score of 0
. You want to perform exactly m
operations. On the ith
operation (1-indexed), you will:
- Choose one integer
x
from either the start or the end of the arraynums
. - Add
multipliers[i] * x
to your score. - Remove
x
from the arraynums
.
Return the maximum score after performing m
operations.
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.
Constraints:
n == nums.length
m == multipliers.length
1 <= m <= 103
m <= n <= 105
-1000 <= nums[i], multipliers[i] <= 1000
Related Topics:
Dynamic Programming
Similar Questions:
This is a search problem and there are overlapping subproblems, so we can use DP to solve it.
Let dp[j][i]
be the maximum score we can get using M[0..j]
and a subarray of A
that starts at i
and has j
elements less than A
(because they are already selected). For the previous j
steps, we already selected j
elements out of A
, and since there are i
selected elements in front of the subarray, there are j - i
selected elements after the subarray. So the index of the last element of the subarray is r = A.size() - j + i - 1
.
dp[j][i] = max(
A[i] * M[j] + dp[i + 1][j + 1], // select A[i]
A[r] * M[j] + dp[i][j + 1], // select A[r]
)
where r = A.size() - j + i - 1
Note:
- The range of
i
is[0, M.size() - 1]
so we just needM
instead ofN
for the second dimension ofdp
. - that for simplicity, we used
0
as unvisited number here. But since0
is a valid score, when thememo[j][i]
is indeed0
, we will recompute the value and thus waste time. We can initializememo[j][i]
toINT_MIN
instead.
// OJ: https://leetcode.com/problems/maximum-score-from-performing-multiplication-operations/
// Author: github.com/lzl124631x
// Time: O(M^2)
// Space: O(M^2)
class Solution {
int memo[1001][1001] = {};
int dfs(vector<int> &A, vector<int> &M, int i, int j) {
if (j == M.size()) return 0;
if (memo[j][i]) return memo[j][i];
return memo[j][i] = max(A[i] * M[j] + dfs(A, M, i + 1, j + 1), A[A.size() - j + i - 1] * M[j] + dfs(A, M, i, j + 1));
}
public:
int maximumScore(vector<int>& A, vector<int>& M) {
return dfs(A, M, 0, 0);
}
};