Maximum Score from Performing Multiplication Operations
You are given two 0-indexed integer arrays nums and multipliers of size n and m respectively, where n >= m.
You begin with a score of 0. You want to perform exactly m operations. On the i^th operation (0-indexed) you will:
- Choose one integer
xfrom either the start or the end of the arraynums. - Add
multipliers[i] * xto your score. - Note that
multipliers[0]corresponds to the first operation,multipliers[1]to the second operation, and so on. - Remove
xfromnums.
Return the maximum score after performing m operations.
Example 1
Input
nums = [1,2,3], multipliers = [3,2,1]Output
14Choosing 3, then 2, then 1 from the end gives a total score of 9 + 4 + 1 = 14.
Example 2
Input
nums = [-5,-3,-3,-2,7,1], multipliers = [-10,-5,3,4,6]Output
102An optimal sequence chooses -5, -3, and -3 from the start, then 1 and 7 from the end, for a total score of 50 + 15 - 9 + 4 + 42 = 102.
Constraints
- n == nums.length
- m == multipliers.length
- 1 <= m <= 300
- m <= n <= 10^5
- -1000 <= nums[i], multipliers[i] <= 1000