LC-1770 Hard LeetCode

1770. Maximum Score from Performing Multiplication Operations

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 42% Topics: Array, Dynamic Programming

Reading material

Arrays & Hashing 12 min 1-D Dynamic Programming 16 min

Reference solution (spoiler · python)

# Time:  O(m^2)
# Space: O(m)

class Solution(object):
    def maximumScore(self, nums, multipliers):
        """
        :type nums: List[int]
        :type multipliers: List[int]
        :rtype: int
        """
        dp = [0]*(len(multipliers)+1)
        for l, m in enumerate(reversed(multipliers), start=len(nums)-len(multipliers)):
            dp = [max(m*nums[i]+dp[i+1], m*nums[i+l]+dp[i]) for i in xrange(len(dp)-1)]
        return dp[0]

Solution from kamyu104/LeetCode-Solutions · MIT