Problem Description

Given two integer arrays, nums (length n) and multipliers (length m), you need to perform m operations. In each operation i (where 0 ≤ i < m), you:

• Pick either the leftmost or rightmost element from nums.
• Multiply it by multipliers[i] and add the result to your score.
• Remove the chosen element from nums (so nums shrinks by one each step).

Your goal is to maximize your total score after exactly m operations.

Constraints:

• Each nums[i] and multipliers[i] can be negative, zero, or positive.
• Each element in nums can only be used once.
• You must use all m multipliers in order, one per operation.
• There is only one valid solution for each input.
• Typical constraints: 1 ≤ m ≤ 10^3, m ≤ n ≤ 10^5.

Thought Process

The problem asks us to maximize a score by making a sequence of left/right picks from nums, each time multiplying by a given multiplier. A brute-force approach would try all possible sequences of left/right picks, but with up to 10^3 picks, this quickly becomes computationally infeasible.

Instead, we notice that at each step, the only decisions are:

• How many picks have we made from the left?
• How many picks have we made from the right?

This insight leads us to dynamic programming: we can cache the results for each state (number of left picks) to avoid recalculating subproblems. This drastically reduces the number of computations compared to brute-force.

Solution Approach

We use dynamic programming (DP) to efficiently solve this problem. Here's how:

1. State Definition:
   • Let dp[left][op] be the maximum score achievable after making op operations, with left picks from the left side of nums (and op - left from the right).
2. Recurrence Relation:
   • At each operation, you can either:
     • Pick from the left: Add nums[left] * multipliers[op] and move to dp[left+1][op+1].
     • Pick from the right: Add nums[n-1-(op-left)] * multipliers[op] and move to dp[left][op+1].

     Take the maximum of both choices.

3. Base Case:
   • When op == m, return 0 (no more picks left).
4. Memoization:
   • We cache the result for each (left, op) pair to avoid redundant computations.
5. Implementation:
   • We can use recursion with memoization (top-down DP), or fill a DP table iteratively (bottom-up DP).
   • Since m is small, our DP table only needs to be size m x m (or even just m if we optimize).

This approach ensures we only compute each subproblem once, making it efficient even for large nums.

Example Walkthrough

Input:
nums = [1, 2, 3], multipliers = [3, 2, 1]

1. Operation 0: Pick left (1*3=3) or right (3*3=9).
   - If left: nums = [2,3], score = 3
   - If right: nums = [1,2], score = 9
2. Operation 1:
   • If previous was left, now pick left (2*2=4) or right (3*2=6).
     - left: nums = [3], score = 3+4=7
     - right: nums = [2], score = 3+6=9
   • If previous was right, now pick left (1*2=2) or right (2*2=4).
     - left: nums = [2], score = 9+2=11
     - right: nums = [1], score = 9+4=13
3. Operation 2:
   • For each remaining possibility, pick the only available element and multiply by 1.
     - [3]: 7+3=10
     - [2]: 9+2=11, 11+2=13
     - [1]: 13+1=14
4. Result:
   The maximum possible score is 14.

Time and Space Complexity

• Brute-force: There are 2 choices (left/right) for each of m steps, so O(2^m) time — infeasible for m = 1000.
• DP Approach: There are at most m possible values for op (step), and for each step, up to op possible values for left (number of left picks). So total subproblems = O(m^2).
  Each subproblem is solved in O(1) time, so total time is O(m^2).
  Space complexity is also O(m^2) for the memoization table.

Summary

The key insight is that, although nums may be very large, the number of operations (m) is small. By framing the problem as a series of left/right picks and using dynamic programming to cache overlapping subproblems, we efficiently compute the maximum possible score. The DP approach transforms an exponential brute-force process into a manageable quadratic solution, making it both elegant and practical.

Code Implementation

from functools import lru_cache

class Solution:
    def maximumScore(self, nums, multipliers):
        n, m = len(nums), len(multipliers)
        
        @lru_cache(None)
        def dp(left, op):
            if op == m:
                return 0
            right = n - 1 - (op - left)
            pick_left = nums[left] * multipliers[op] + dp(left + 1, op + 1)
            pick_right = nums[right] * multipliers[op] + dp(left, op + 1)
            return max(pick_left, pick_right)
        
        return dp(0, 0)
    

class Solution {
public:
    int maximumScore(vector<int>& nums, vector<int>& multipliers) {
        int n = nums.size(), m = multipliers.size();
        vector<vector<int>> dp(m+1, vector<int>(m+1, INT_MIN));
        
        function<int(int, int)> solve = [&](int left, int op) {
            if (op == m) return 0;
            if (dp[left][op] != INT_MIN) return dp[left][op];
            int right = n - 1 - (op - left);
            int pick_left = nums[left] * multipliers[op] + solve(left + 1, op + 1);
            int pick_right = nums[right] * multipliers[op] + solve(left, op + 1);
            return dp[left][op] = max(pick_left, pick_right);
        };
        return solve(0, 0);
    }
};
    

class Solution {
    public int maximumScore(int[] nums, int[] multipliers) {
        int n = nums.length, m = multipliers.length;
        Integer[][] memo = new Integer[m + 1][m + 1];
        
        return dp(0, 0, nums, multipliers, memo, n, m);
    }
    
    private int dp(int left, int op, int[] nums, int[] multipliers, Integer[][] memo, int n, int m) {
        if (op == m) return 0;
        if (memo[left][op] != null) return memo[left][op];
        int right = n - 1 - (op - left);
        int pickLeft = nums[left] * multipliers[op] + dp(left + 1, op + 1, nums, multipliers, memo, n, m);
        int pickRight = nums[right] * multipliers[op] + dp(left, op + 1, nums, multipliers, memo, n, m);
        return memo[left][op] = Math.max(pickLeft, pickRight);
    }
}
    

var maximumScore = function(nums, multipliers) {
    const n = nums.length, m = multipliers.length;
    const memo = Array.from({length: m + 1}, () => Array(m + 1).fill(undefined));
    
    function dp(left, op) {
        if (op === m) return 0;
        if (memo[left][op] !== undefined) return memo[left][op];
        const right = n - 1 - (op - left);
        const pickLeft = nums[left] * multipliers[op] + dp(left + 1, op + 1);
        const pickRight = nums[right] * multipliers[op] + dp(left, op + 1);
        memo[left][op] = Math.max(pickLeft, pickRight);
        return memo[left][op];
    }
    return dp(0, 0);
};