Problem

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

You begin with a score of 0. You want to perform exactly m operations. On the ith operation (0-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.
    • Note that multipliers[0] corresponds to the first operation, multipliers[1] to the second operation, and so on.
  • Remove x from 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 – Dynamic Programming 1

Intuition

The problem asks us to maximize the score by picking elements from either end of the array for each operation. Since each choice affects future choices, dynamic programming is ideal to explore all possibilities efficiently.

Approach

  1. Use a DP table where dp[i][l] represents the maximum score after i operations, having picked l elements from the left.
  2. For each operation, either pick from the left or right and update the DP table accordingly.
  3. The right index is determined by the number of picks from the left and the current operation.
  4. The answer is the maximum value after all operations.

Code

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

class Solution {
public:
    int maximumScore(vector<int>& nums, vector<int>& multipliers) {
        int m = multipliers.size(), n = nums.size();
        vector<vector<int>> dp(m+1, vector<int>(m+1, 0));
        for (int i = m-1; i >= 0; --i) {
            for (int l = i; l >= 0; --l) {
                int r = n-1-(i-l);
                dp[i][l] = max(
                    multipliers[i]*nums[l] + dp[i+1][l+1],
                    multipliers[i]*nums[r] + dp[i+1][l]
                );
            }
        }
        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 {
    m, n := len(multipliers), len(nums)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, m+1)
    }
    for i := m-1; i >= 0; i-- {
        for l := i; l >= 0; l-- {
            r := n-1-(i-l)
            left := multipliers[i]*nums[l] + dp[i+1][l+1]
            right := multipliers[i]*nums[r] + dp[i+1][l]
            if left > right {
                dp[i][l] = left
            } else {
                dp[i][l] = right
            }
        }
    }
    return dp[0][0]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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

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

def maximumScore(nums: list[int], multipliers: list[int]) -> int:
    m, n = len(multipliers), len(nums)
    dp = [[0]*(m+1) for _ in range(m+1)]
    for i in range(m-1, -1, -1):
        for l in range(i, -1, -1):
            r = n-1-(i-l)
            left = multipliers[i]*nums[l] + dp[i+1][l+1]
            right = multipliers[i]*nums[r] + dp[i+1][l]
            dp[i][l] = max(left, 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 m = multipliers.len();
        let n = nums.len();
        let mut dp = vec![vec![0; m+1]; m+1];
        for i in (0..m).rev() {
            for l in (0..=i).rev() {
                let r = n-1-(i-l);
                let left = multipliers[i]*nums[l] + dp[i+1][l+1];
                let right = multipliers[i]*nums[r] + dp[i+1][l];
                dp[i][l] = left.max(right);
            }
        }
        dp[0][0]
    }
}
 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 m = multipliers.length, n = nums.length;
        const dp: number[][] = Array.from({length: m+1}, () => Array(m+1).fill(0));
        for (let i = m-1; i >= 0; i--) {
            for (let l = i; l >= 0; l--) {
                const r = n-1-(i-l);
                dp[i][l] = Math.max(
                    multipliers[i]*nums[l] + dp[i+1][l+1],
                    multipliers[i]*nums[r] + dp[i+1][l]
                );
            }
        }
        return dp[0][0];
    }
}

Complexity

  • ⏰ Time complexity: O(m^2), since for each operation and left pick, we fill the DP table.
  • 🧺 Space complexity: O(m^2), for the DP table.