This 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.
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.
1#include <stdio.h>
2#include <stdlib.h>
3
4int max(int a, int b) { return a > b ? a : b; }
5
6int maximumScore(int* nums, int numsSize, int* multipliers, int multipliersSize) {
7 int m = multipliersSize;
8 int** dp = (int**)malloc((m + 1) * sizeof(int*));
9 for (int i = 0; i <= m; ++i) dp[i] = (int*)calloc((m + 1), sizeof(int));
10 for (int i = m - 1; i >= 0; --i) {
11 for (int left = i; left >= 0; --left) {
12 dp[i][left] = max(
13 multipliers[i] * nums[left] + dp[i + 1][left + 1],
14 multipliers[i] * nums[numsSize - 1 - (i - left)] + dp[i + 1][left]
15 );
16 }
17 }
18 int result = dp[0][0];
19 for (int i = 0; i <= m; ++i) free(dp[i]);
20 free(dp);
21 return result;
22}This C solution mimics the logic of earlier solutions by using dynamic programming. It allocates space for an m x m DP matrix to store the maximum scores possible at each step by choosing either from the start or the end of the 'nums'. Finally, it returns the maximum score computed in dp[0][0].
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.
Time Complexity: O(m), where m is the number of operations.
Space Complexity: O(1), utilizing constant space regardless of input size.
1function maximumScore(nums, multipliers) {
2 let left = 0, right = nums.length - 1;
3 let score = 0;
4 for (let multiplier of multipliers) {
5 if (multiplier * nums[left] >= multiplier * nums[right]) {
6 score += multiplier * nums[left];
7 left += 1;
8 } else {
9 score += multiplier * nums[right];
10 right -= 1;
11 }
12 }
13 return score;
14}This approach uses a liner traversal greedy technique, continually updating the score by evaluating whether the current multiplier would yield a higher contribution by multiplying it with the element at the start versus the element on the end of the nums array.