<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 maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
        # perform m = len(multipliers)
        # choose x = nums[0] or x = nums[-1]
        # multiplier[i] * x

        # [1, 2, 3] - nums
        # [3, 2, 1] - multipliers

        # start from multiplier position
        # 3 - > max(mult[i] * nums[0], mult[i] * nums[-1]) -> (3 * 1, 3 * 3) = 9
        # nums = [1, 2]
        # 2 -> max(mult[i] * nums[0], mult[i] * nums[-1]) -> (2 * 1, 2 * 2) = 2
        # nums = [1]


        # ----

        # nums = [-5,-3,-3,-2,7,1]
        # multipliers = [-10,-5,3,4,6]

        # -10 = max(-10 * -5, -10 * 1) -> 50
        # nums [-3 -3 -2 7 1]
        # -5 = max(-5 * -3, -5 * 1) -> 15 
        # nums = [-3 -3 -2 7 1]
        # 3 = max(3 * -3, 3 * 1) -> 3 (!)
        # nums = [-3 -3 -2]
        # 4 = max(4 * -3 , 4 * -2) -> -8

        # at each state we need to do multiplication 
        # it is better to first multiply the 
        # smallest should be multiplied with the smallest
        @lru_cache(2000)
        def dp(m_idx, left):
            if m_idx == len(multipliers):
                return 0

            right = len(nums) - 1 - (m_idx - left)
            mul = multipliers[m_idx]


            return max(dp(m_idx + 1, left + 1) + mul * nums[left], dp(m_idx + 1, left) + mul * nums[right])
        
        return dp(0, 0)

42665