<p>You are given two <strong>0-indexed</strong> integer arrays <code>nums</code> and <code>multipliers</code><strong> </strong>of size <code>n</code> and <code>m</code> respectively, where <code>n &gt;= m</code>.</p>

<p>You begin with a score of <code>0</code>. You want to perform <strong>exactly</strong> <code>m</code> operations. On the <code>i<sup>th</sup></code> operation (<strong>0-indexed</strong>) you will:</p>

<ul>
    <li>Choose one integer <code>x</code> from <strong>either the start or the end </strong>of the array <code>nums</code>.</li>
    <li>Add <code>multipliers[i] * x</code> to your score.
    <ul>
        <li>Note that <code>multipliers[0]</code> corresponds to the first operation, <code>multipliers[1]</code> to the second operation, and so on.</li>
    </ul>
    </li>
    <li>Remove <code>x</code> from <code>nums</code>.</li>
</ul>

<p>Return <em>the <strong>maximum</strong> score after performing </em><code>m</code> <em>operations.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3], multipliers = [3,2,1]
<strong>Output:</strong> 14
<strong>Explanation:</strong>&nbsp;An optimal solution is as follows:
- Choose from the end, [1,2,<strong><u>3</u></strong>], adding 3 * 3 = 9 to the score.
- Choose from the end, [1,<strong><u>2</u></strong>], adding 2 * 2 = 4 to the score.
- Choose from the end, [<strong><u>1</u></strong>], adding 1 * 1 = 1 to the score.
The total score is 9 + 4 + 1 = 14.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [-5,-3,-3,-2,7,1], multipliers = [-10,-5,3,4,6]
<strong>Output:</strong> 102
<strong>Explanation: </strong>An optimal solution is as follows:
- Choose from the start, [<u><strong>-5</strong></u>,-3,-3,-2,7,1], adding -5 * -10 = 50 to the score.
- Choose from the start, [<strong><u>-3</u></strong>,-3,-2,7,1], adding -3 * -5 = 15 to the score.
- Choose from the start, [<strong><u>-3</u></strong>,-2,7,1], adding -3 * 3 = -9 to the score.
- Choose from the end, [-2,7,<strong><u>1</u></strong>], adding 1 * 4 = 4 to the score.
- Choose from the end, [-2,<strong><u>7</u></strong>], adding 7 * 6 = 42 to the score. 
The total score is 50 + 15 - 9 + 4 + 42 = 102.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == nums.length</code></li>
	<li><code>m == multipliers.length</code></li>
	<li><code>1 &lt;= m &lt;= 300</code></li>
	<li><code>m &lt;= n &lt;= 10<sup>5</sup></code><code> </code></li>
	<li><code>-1000 &lt;= nums[i], multipliers[i] &lt;= 1000</code></li>
</ul>

class Solution:
    # def _dp(self, nums, mults, n_index, m_index, cache=None):
    #     if cache is None:
    #         cache = {}
    #     if (n_index, m_index) in cache:
    #         return cache[(n_index, m_index)]
    #     if m_index == len(mults) - 1:
    #         res = [nums[n_index[0]], nums[n_index[1]]]
    #         res = sorted([mults[m_index] * n for n in res])
    #     else:
    #         left = self._dp(
    #             nums, mults,
    #             (n_index[0] + 1, n_index[1]), m_index + 1,
    #             cache
    #         )
    #         right = self._dp(
    #             nums, mults,
    #             (n_index[0], n_index[1] - 1), m_index + 1,
    #             cache
    #         )
    #         v = nums[n_index[0]] * mults[m_index] 
    #         left = [v + l for l in left]
    #         v = nums[n_index[1]] * mults[m_index]
    #         right = [v + l for l in right]
    #         res = [min([*left, *right]), max([*left, *right])]
        
    #     cache[(n_index, m_index)] = res
    #     return res

    def maximumScore2(self, nums: List[int], multipliers: List[int]) -> int:
        pass
        # cache = {}
        # res = self._dp(nums, multipliers, (0, len(nums) - 1), 0, cache)
        # # print(cache)
        # return max(res)
        # dp = {}
        # m_index = len(multipliers) - 1
        # dp[m_index] = {}
        # for left in range(m_index + 1):
        #     right = left + len(nums) - m_index - 1
        #     res = [n * multipliers[m_index] for n in [nums[left], nums[right]]]
        #     res.sort()
        #     dp[m_index][(left, right)] = res
        
        # for m_index in range(len(multipliers) - 2, -1, -1):
        #     dp[m_index] = {}
        #     for left in range(m_index + 1):
        #         right = left + len(nums) - m_index - 1
        #         option_1 = [
        #             multipliers[m_index] * nums[left] + r for r in dp[m_index + 1][(left + 1, right)]
        #         ]
        #         option_2 = [
        #             multipliers[m_index] * nums[right] + r for r in dp[m_index + 1][(left, right - 1)]
        #         ]
        #         res = [*option_1, *option_2]
        #         res = [min(res), max(res)]
        #         dp[m_index][(left, right)] = res
        #     dp.pop(m_index + 1)
        # # print(dp)
        # sol = float('-inf')
        # for _, vals in dp[0].items():
        #     sol = max(sol, max(vals))
        # return sol

    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
        # N = len(nums) - 1
        # M = len(multipliers) - 1
        # def dp(l, r, cache=None):
        #     if cache is None:
        #         cache = {}
        #     i = min(l + N - r, M)
        #     # print(l, r, i)
        #     if (l, r) in cache:
        #         return cache[(l, r, i)]
        #     if i == M:
        #         return max(
        #             nums[l] * multipliers[i],
        #             nums[r] * multipliers[i]
        #         )
        #     if l == r:
        #         return nums[l] * multipliers[i]
        #     cache[(l, r)] = max(
        #         nums[l] * multipliers[i] + dp(l + 1, r),
        #         nums[r] * multipliers[i] + dp(l, r - 1)
        #     )
        #     return cache[(l, r)]
        # return dp(0, N)
        # @cache
        def dp(i, left, cache=None):
            if cache is None:
                cache = {}
            if (i, left) in cache:
                return cache[(i, left)]
            # Base case
            if i == m:
                return 0

            mult = multipliers[i]
            right = n - 1 - (i - left)
            
            # Recurrence relation
            cache[(i, left)] = max(
                mult * nums[left] + dp(i + 1, left + 1, cache), 
                mult * nums[right] + dp(i + 1, left, cache)
            )
            return cache[(i, left)]
            # return max(
            #     mult * nums[left] + dp(i + 1, left + 1), 
            #     mult * nums[right] + dp(i + 1, left)
            # )
                       
        n, m = len(nums), len(multipliers)
        return dp(0, 0)
        
1104