2026-01-08 15:42:20 +0300 MSK

class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        cache = {}

        def dp(i: int, j: int):
            if i == len(nums1) or j == len(nums2):
                return float("-inf")
            if (i, j) in cache:
                return cache[(i, j)]
            take = nums1[i] * nums2[j]
            res = max(take + dp(i+1, j+1), take, dp(i+1,j), dp(i,j+1))
            cache[(i, j)] = res
            return cache[(i, j)]

        return dp(0,0)