Problem

You are given two integer arrays nums and multipliers of size n and m respectively, where n >= m. The arrays are 1-indexed.

You begin with a score of 0. You want to perform exactly m operations. On the ith operation (1-indexed), you will:

  • Choose one integer x from either the start or the end of the array nums.
  • Add multipliers[i] * x to your score.
  • Remove x from the array nums.

Return the maximum score after performing m operations.

Examples

Example 1:

1
2
3
4
5
6
7
8
9

Input:
nums = [1,2,3], multipliers = [3,2,1]
Output:
 14
Explanation: An optimal solution is as follows:
- Choose from the end, [1,2,**3**], adding 3 * 3 = 9 to the score.
- Choose from the end, [1,**2**], adding 2 * 2 = 4 to the score.
- Choose from the end, [**1**], adding 1 * 1 = 1 to the score.
The total score is 9 + 4 + 1 = 14.

Example 2:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

Solution

Method 1 - Try Greedy (which Fails ❌)

We can use two pointers, left and right, for the two ends of the array. At each step, we pick an integer x from either end of nums and multiply it by multipliers[i]. The idea is to always pick the larger x from either end.

Is this correct? Not always! Since both nums[i] and multipliers[i] can be negative (as per the constraints -1000 ≤ nums[i], multipliers[i] ≤ 1000), sometimes picking a smaller absolute value or a negative number is better, depending on the sign of multipliers[i]. For example, if multipliers[i] is -10, choosing -3 gives 30, which is better than choosing -5 and getting 50 (since we want the maximum score).

Dry Run 1

Input: nums = [1, 2, 3], multipliers = [3, 2, 1] Step-by-step:

  • For multipliers[0] = 3, choose nums[2] = 3 (end), add 3 * 3 = 9.
  • For multipliers[1] = 2, choose nums[1] = 2 (end), add 2 * 2 = 4.
  • For multipliers[2] = 1, choose nums[0] = 1 (end), add 1 * 1 = 1.

Total score: 9 + 4 + 1 = 14 (Correct ✅)

Dry Run 2

Input: nums = [-5, -3, -3, -2, 7, 1], multipliers = [-10, -5, 3, 4, 6] Step-by-step:

  • For multipliers[0] = -10, choose nums[0] = -5 (start), add -5 * -10 = 50.
  • For multipliers[1] = -5, choose nums[0] = -3 (start), add -3 * -5 = 15.
  • For multipliers[2] = 3, choose nums[3] = 1 (end), add 1 * 3 = 3.
  • For multipliers[3] = 4, choose nums[2] = 7 (end), add 7 * 4 = 28.
  • For multipliers[4] = 6, choose nums[1] = -2 (end), add -2 * 6 = -12.

Total score: 50 + 15 + 3 + 28 + (-12) = 84, which is not optimal (the correct answer is 102). ❌

Greedy Failed

This was discussed on Computer Science Stack Exchange, and the answer and comments note:

  • “To show that the greedy approach fails, all you have to do is come up with a counterexample.”
  • “To prove that the greedy algorithm is not optimal, it suffices to give one counterexample.”
  • “To prove that the greedy algorithm is not optimal, it suffices to give one counterexample”

Method 2 - Top Down DP

Intuition

The greedy approach fails because the optimal choice at each step depends on future decisions. Dynamic programming works here because the problem has overlapping subproblems and optimal substructure: the best score for a given state depends only on the choices made so far, not on the order. By storing results for each state, we avoid redundant calculations.

Approach

  1. Use recursion with memoization to explore all possible ways to pick elements from either end of nums for each operation.
  2. Define the state by two variables:
    • i: number of operations performed so far (index in multipliers)
    • l: number of elements taken from the left of nums
    • The right index is calculated as r = n - 1 - (i - l)
  3. At each step, choose either:
    • Take from the left: add nums[l] * multipliers[i] and recurse with i+1, l+1
    • Take from the right: add nums[r] * multipliers[i] and recurse with i+1, l
  4. Memoize results for each (i, l) to avoid recomputation.
  5. Base case: if all operations are done (i == m), return 0.

The recurrence relation for this DP can be visualized as:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int maximumScore(vector<int>& nums, vector<int>& multipliers) {
        int n = nums.size(), m = multipliers.size();
        vector<vector<int>> memo(m+1, vector<int>(m+1, INT_MIN));
        function<int(int,int)> dfs = [&](int i, int l) {
            if (i == m) return 0;
            if (memo[i][l] != INT_MIN) return memo[i][l];
            int r = n - 1 - (i - l);
            int left = nums[l] * multipliers[i] + dfs(i+1, l+1);
            int right = nums[r] * multipliers[i] + dfs(i+1, l);
            return memo[i][l] = max(left, right);
        };
        return dfs(0, 0);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

func maximumScore(nums []int, multipliers []int) int {
    n, m := len(nums), len(multipliers)
    memo := make([][]int, m+1)
    for i := range memo {
        memo[i] = make([]int, m+1)
        for j := range memo[i] {
            memo[i][j] = -1 << 31
        }
    }
    var dfs func(i, l int) int
    dfs = func(i, l int) int {
        if i == m {
            return 0
        }
        if memo[i][l] != -1<<31 {
            return memo[i][l]
        }
        r := n - 1 - (i - l)
        left := nums[l]*multipliers[i] + dfs(i+1, l+1)
        right := nums[r]*multipliers[i] + dfs(i+1, l)
        if left > right {
            memo[i][l] = left
        } else {
            memo[i][l] = right
        }
        return memo[i][l]
    }
    return dfs(0, 0)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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 dfs(nums, multipliers, 0, 0, memo);
    }
    private int dfs(int[] nums, int[] multipliers, int i, int l, Integer[][] memo) {
        if (i == multipliers.length) return 0;
        if (memo[i][l] != null) return memo[i][l];
        int r = nums.length - 1 - (i - l);
        int left = nums[l] * multipliers[i] + dfs(nums, multipliers, i+1, l+1, memo);
        int right = nums[r] * multipliers[i] + dfs(nums, multipliers, i+1, l, memo);
        return memo[i][l] = Math.max(left, right);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    fun maximumScore(nums: IntArray, multipliers: IntArray): Int {
        val n = nums.size
        val m = multipliers.size
        val memo = Array(m+1) { Array(m+1) { null as Int? } }
        fun dfs(i: Int, l: Int): Int {
            if (i == m) return 0
            memo[i][l]?.let { return it }
            val r = n - 1 - (i - l)
            val left = nums[l] * multipliers[i] + dfs(i+1, l+1)
            val right = nums[r] * multipliers[i] + dfs(i+1, l)
            val ans = maxOf(left, right)
            memo[i][l] = ans
            return ans
        }
        return dfs(0, 0)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def maximumScore(self, nums: list[int], multipliers: list[int]) -> int:
        n, m = len(nums), len(multipliers)
        memo: dict[tuple[int, int], int] = {}
        def dfs(i: int, l: int) -> int:
            if i == m:
                return 0
            if (i, l) in memo:
                return memo[(i, l)]
            r = n - 1 - (i - l)
            left = nums[l] * multipliers[i] + dfs(i+1, l+1)
            right = nums[r] * multipliers[i] + dfs(i+1, l)
            memo[(i, l)] = max(left, right)
            return memo[(i, l)]
        return dfs(0, 0)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn maximum_score(nums: Vec<i32>, multipliers: Vec<i32>) -> i32 {
        let n = nums.len();
        let m = multipliers.len();
        let mut memo = vec![vec![None; m+1]; m+1];
        fn dfs(i: usize, l: usize, nums: &Vec<i32>, multipliers: &Vec<i32>, memo: &mut Vec<Vec<Option<i32>>>) -> i32 {
            if i == multipliers.len() { return 0; }
            if let Some(val) = memo[i][l] { return val; }
            let r = nums.len() - 1 - (i - l);
            let left = nums[l] * multipliers[i] + dfs(i+1, l+1, nums, multipliers, memo);
            let right = nums[r] * multipliers[i] + dfs(i+1, l, nums, multipliers, memo);
            let ans = left.max(right);
            memo[i][l] = Some(ans);
            ans
        }
        dfs(0, 0, &nums, &multipliers, &mut memo)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    maximumScore(nums: number[], multipliers: number[]): number {
        const n = nums.length, m = multipliers.length;
        const memo: (number | undefined)[][] = Array.from({length: m+1}, () => Array(m+1));
        function dfs(i: number, l: number): number {
            if (i === m) return 0;
            if (memo[i][l] !== undefined) return memo[i][l]!;
            const r = n - 1 - (i - l);
            const left = nums[l] * multipliers[i] + dfs(i+1, l+1);
            const right = nums[r] * multipliers[i] + dfs(i+1, l);
            memo[i][l] = Math.max(left, right);
            return memo[i][l]!;
        }
        return dfs(0, 0);
    }
}

Complexity

  • ⏰ Time complexity: O(m^2) — There are m operations and for each, up to m possible left picks, so the DP table is m x m.
  • 🧺 Space complexity: O(m^2) — The memoization table stores results for each (i, l) pair.

Method 3 - Bottom Up DP

Intuition

This method uses bottom-up dynamic programming to avoid recursion and stack overhead. By iteratively filling a table, we build up solutions for smaller subproblems and use them to solve larger ones. The key is that the optimal score for each state depends only on the choices made so far, and we can compute these efficiently in reverse order.

Approach

  1. Create a 2D DP table dp where dp[i][left] stores the maximum score after i operations and left picks from the left.
  2. Iterate backwards over the number of operations (i from m-1 to 0).
  3. For each possible number of left picks (left from 0 to i):
    • Compute the right index as right = n - 1 - (i - left).
    • Update memo[i][left] as the maximum of:
      • Picking from the left: nums[left] * multipliers[i] + memo[i+1][left+1]
      • Picking from the right: nums[right] * multipliers[i] + memo[i+1][left]
  4. The answer is stored in memo[0][0].
  5. For space optimization, use a 1D array and update in place.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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, 0));
        for (int i = m-1; i >= 0; --i) {
            for (int left = i; left >= 0; --left) {
                int right = n - 1 - (i - left);
                int pickLeft = nums[left] * multipliers[i] + dp[i+1][left+1];
                int pickRight = nums[right] * multipliers[i] + dp[i+1][left];
                dp[i][left] = max(pickLeft, pickRight);
            }
        }
        return dp[0][0];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func maximumScore(nums []int, multipliers []int) int {
    n, m := len(nums), len(multipliers)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, m+1)
    }
    for i := m-1; i >= 0; i-- {
        for left := i; left >= 0; left-- {
            right := n - 1 - (i - left)
            pickLeft := nums[left]*multipliers[i] + dp[i+1][left+1]
            pickRight := nums[right]*multipliers[i] + dp[i+1][left]
            if pickLeft > pickRight {
                dp[i][left] = pickLeft
            } else {
                dp[i][left] = pickRight
            }
        }
    }
    return dp[0][0]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int maximumScore(int[] nums, int[] multipliers) {
        int n = nums.length, m = multipliers.length;
        int[][] dp = new int[m+1][m+1];
        for (int i = m-1; i >= 0; i--) {
            for (int left = i; left >= 0; left--) {
                int right = n - 1 - (i - left);
                int pickLeft = nums[left] * multipliers[i] + dp[i+1][left+1];
                int pickRight = nums[right] * multipliers[i] + dp[i+1][left];
                dp[i][left] = Math.max(pickLeft, pickRight);
            }
        }
        return dp[0][0];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun maximumScore(nums: IntArray, multipliers: IntArray): Int {
        val n = nums.size
        val m = multipliers.size
        val dp = Array(m+1) { IntArray(m+1) }
        for (i in m-1 downTo 0) {
            for (left in i downTo 0) {
                val right = n - 1 - (i - left)
                val pickLeft = nums[left] * multipliers[i] + dp[i+1][left+1]
                val pickRight = nums[right] * multipliers[i] + dp[i+1][left]
                dp[i][left] = maxOf(pickLeft, pickRight)
            }
        }
        return dp[0][0]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def maximumScore(self, nums: list[int], multipliers: list[int]) -> int:
        n, m = len(nums), len(multipliers)
        dp = [[0] * (m+1) for _ in range(m+1)]
        for i in range(m-1, -1, -1):
            for left in range(i, -1, -1):
                right = n - 1 - (i - left)
                pick_left = nums[left] * multipliers[i] + dp[i+1][left+1]
                pick_right = nums[right] * multipliers[i] + dp[i+1][left]
                dp[i][left] = max(pick_left, pick_right)
        return dp[0][0]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn maximum_score(nums: Vec<i32>, multipliers: Vec<i32>) -> i32 {
        let n = nums.len();
        let m = multipliers.len();
        let mut dp = vec![vec![0; m+1]; m+1];
        for i in (0..m).rev() {
            for left in (0..=i).rev() {
                let right = n - 1 - (i - left);
                let pick_left = nums[left] * multipliers[i] + dp[i+1][left+1];
                let pick_right = nums[right] * multipliers[i] + dp[i+1][left];
                dp[i][left] = pick_left.max(pick_right);
            }
        }
        dp[0][0]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    maximumScore(nums: number[], multipliers: number[]): number {
        const n = nums.length, m = multipliers.length;
        const dp: number[][] = Array.from({length: m+1}, () => Array(m+1).fill(0));
        for (let i = m-1; i >= 0; i--) {
            for (let left = i; left >= 0; left--) {
                const right = n - 1 - (i - left);
                const pickLeft = nums[left] * multipliers[i] + dp[i+1][left+1];
                const pickRight = nums[right] * multipliers[i] + dp[i+1][left];
                dp[i][left] = Math.max(pickLeft, pickRight);
            }
        }
        return dp[0][0];
    }
}

Complexity

  • ⏰ Time complexity: O(m^2) — We fill a table of size m x m.
  • 🧺 Space complexity: O(m^2) — The memoization table is m x m. With space optimization, it can be reduced to O(m).