1770. Max Score from Multiplication Operations
Question
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 i<sup>th</sup>
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.
Solution
动态规划,dp[][]数组记录左边取的个数和右边取的个数。
从取1开始到取multipliers的长度位置开始遍历。
然后从left取0个开始,直到left取i个为止遍历。
计算对应的right指针位置。
注意访问数组时需要访问left和right的上一个位置。
如果left为0,则只能取右侧的上一个位置加上右侧的上一个数值乘以mul。
如果right为0,则只能取左侧的上一个位置加上左侧的上一个数值乘以mul。
否则取两者之间的最大值。
最后遍历数组中left + right和为m的位置,并返回最大值。
Code
1 | class Solution { |