1770. Max Score from Multiplication Operations

Question

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 i<sup>th</sup> 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.

Solution

动态规划，dp[][]数组记录左边取的个数和右边取的个数。

从取1开始到取multipliers的长度位置开始遍历。
然后从left取0个开始，直到left取i个为止遍历。
计算对应的right指针位置。

注意访问数组时需要访问left和right的上一个位置。

如果left为0，则只能取右侧的上一个位置加上右侧的上一个数值乘以mul。
如果right为0，则只能取左侧的上一个位置加上左侧的上一个数值乘以mul。
否则取两者之间的最大值。

最后遍历数组中left + right和为m的位置，并返回最大值。

Code

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 = 1; i <= m; i++){
            int mul = multipliers[i-1];
            for(int l = 0; l <= i; l++){
                int r = i - l;
                int iL = l - 1, iR = n - r;
                if(l == 0) dp[l][r] = dp[l][r-1] + mul * nums[iR];
                else if(r == 0) dp[l][r] = dp[l-1][r] + mul * nums[iL];
                else dp[l][r] = Math.max(dp[l-1][r] + mul * nums[iL], dp[l][r-1] + mul * nums[iR]);
            }
        }
        int ans = Integer.MIN_VALUE;
        for(int l = 1; l <= m; l++){
            int r = m - l;
            ans = Math.max(ans, dp[l][r]);
        }
        return ans;
    }
}