1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
# 1770. Maximum Score from Performing Multiplication Operations
"""
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, you will choose one integer x
from either the start or the end of the array 'nums'. add 'multipliers[i]
x' to your score. note that 'multipliers[0]' correspons to the first
operation, 'multipliers[1]' to the second operation and so on. return the
maximum score after performing m operations.
"""
class Solution(object):
def maximumScore(self, nums, multipliers):
"""
:type nums: List[int]
:type multipliers: List[int]
:rtype: int
"""
n, m = len(nums), len(multipliers)
dp = [[0] * (m + 1) for _ in range(m + 1)]
for l in range(m - 1, -1, -1):
for i in range(m - 1, -1, -1):
r = n - (i - l) - 1
if r < 0 or r >= n:
break
leftPick = dp[l + 1][i + 1] + nums[l] * multipliers[i]
rightPick = dp[l][i + 1] + nums[r] * multipliers[i]
dp[l][i] = max(leftPick, rightPick)
return dp[0][0]
if __name__ == "__main__":
obj = Solution()
print(obj.maximumScore(nums=[1, 2, 3], multipliers=[3, 2, 1]))
print(obj.maximumScore(nums=[-5, -3, -3, -2, 7, 1], multipliers=[-10, -5, 3, 4, 6]))
|