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:
x from either the start or the end of the array nums.multipliers[i] * x to your score.
multipliers[0] corresponds to the first operation, multipliers[1] to the second operation, and so on.x from nums.Return the maximum score after performing m operations.
Example 1:
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:
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.
Constraints:
n == nums.lengthm == multipliers.length1 <= m <= 300m <= n <= 105 -1000 <= nums[i], multipliers[i] <= 1000This approach involves using dynamic programming to keep track of the maximum scores obtainable by choosing elements from either the start or the end of the nums array during each step of the operations defined by the multipliers array. We maintain a 2D DP table where dp[i][j] represents the maximum score obtained by using the first (i + j) elements from nums, where i elements have been chosen from the start, and j elements have been chosen from the end.
The function maximum_score initializes a 2D array dp with dimensions (m+1) x (m+1). We iterate through the operations and the elements chosen from the start. For each combination of choices, we compute the score achievable by either picking from the start or end. We fill up the DP table backwards, taking the maximum of both potential choices.
C++
Java
C
JavaScript
C#
Time Complexity: O(m^2), where m is the length of the multipliers array, because we're filling an m x m DP table.
Space Complexity: O(m^2) due to the storage requirements of the m x m DP table.
This approach uses a simpler greedy strategy to try and choose the best possible option at each step, based on examining both the start and end of the nums array for potential scores. It evaluates which element, when multiplied with the current multiplier, gives the maximum increase in the score and selects that iteratively through all operations.
The function computes the maximum playable score using a greedy method that goes through each multiplier in the multipliers array. At each step, it determines whether picking the starting element or the ending element in the nums array yields a better score and then opts for that choice until all operations are exhausted.
C++
Java
C
JavaScript
C#
Time Complexity: O(m), where m is the number of operations.
Space Complexity: O(1), utilizing constant space regardless of input size.
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(m^2), where m is the length of the multipliers array, because we're filling an m x m DP table. |
| Greedy Approach | Time Complexity: O(m), where m is the number of operations. |
Leetcode 1770. Maximum Score from Performing Multiplication Operations • Fraz • 10,993 views views
Watch 9 more video solutions →Practice Maximum Score from Performing Multiplication Operations with our built-in code editor and test cases.
Practice on FleetCode