Question

1770. Maximum Score from Performing Multiplication Operations

中文文档

Description

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._

 

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.length
• m == multipliers.length
• 1 <= m <= 300
• m <= n <= 105
• -1000 <= nums[i], multipliers[i] <= 1000

Solutions

Solution 1

class Solution:
  def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
    @cache
    def f(i, j, k):
      if k >= m or i >= n or j < 0:
        return 0
      a = f(i + 1, j, k + 1) + nums[i] * multipliers[k]
      b = f(i, j - 1, k + 1) + nums[j] * multipliers[k]
      return max(a, b)

    n = len(nums)
    m = len(multipliers)
    return f(0, n - 1, 0)

class Solution {
  private Integer[][] f;
  private int[] multipliers;
  private int[] nums;
  private int n;
  private int m;

  public int maximumScore(int[] nums, int[] multipliers) {
    n = nums.length;
    m = multipliers.length;
    f = new Integer[m][m];
    this.nums = nums;
    this.multipliers = multipliers;
    return dfs(0, 0);
  }

  private int dfs(int i, int j) {
    if (i >= m || j >= m || (i + j) >= m) {
      return 0;
    }
    if (f[i][j] != null) {
      return f[i][j];
    }
    int k = i + j;
    int a = dfs(i + 1, j) + nums[i] * multipliers[k];
    int b = dfs(i, j + 1) + nums[n - 1 - j] * multipliers[k];
    f[i][j] = Math.max(a, b);
    return f[i][j];
  }
}

class Solution {
public:
  int maximumScore(vector<int>& nums, vector<int>& multipliers) {
    int n = nums.size(), m = multipliers.size();
    int f[m][m];
    memset(f, 0x3f, sizeof f);
    function<int(int, int)> dfs = [&](int i, int j) -> int {
      if (i >= m || j >= m || (i + j) >= m) return 0;
      if (f[i][j] != 0x3f3f3f3f) return f[i][j];
      int k = i + j;
      int a = dfs(i + 1, j) + nums[i] * multipliers[k];
      int b = dfs(i, j + 1) + nums[n - j - 1] * multipliers[k];
      return f[i][j] = max(a, b);
    };
    return dfs(0, 0);
  }
};

func maximumScore(nums []int, multipliers []int) int {
  n, m := len(nums), len(multipliers)
  f := make([][]int, m)
  for i := range f {
    f[i] = make([]int, m)
    for j := range f[i] {
      f[i][j] = 1 << 30
    }
  }
  var dfs func(i, j int) int
  dfs = func(i, j int) int {
    if i >= m || j >= m || i+j >= m {
      return 0
    }
    if f[i][j] != 1<<30 {
      return f[i][j]
    }
    k := i + j
    a := dfs(i+1, j) + nums[i]*multipliers[k]
    b := dfs(i, j+1) + nums[n-j-1]*multipliers[k]
    f[i][j] = max(a, b)
    return f[i][j]
  }
  return dfs(0, 0)
}

function maximumScore(nums: number[], multipliers: number[]): number {
  const inf = 1 << 30;
  const n = nums.length;
  const m = multipliers.length;
  const f = new Array(m + 1).fill(0).map(() => new Array(m + 1).fill(-inf));
  f[0][0] = 0;
  let ans = -inf;
  for (let i = 0; i <= m; ++i) {
    for (let j = 0; j <= m - i; ++j) {
      const k = i + j - 1;
      if (i > 0) {
        f[i][j] = Math.max(f[i][j], f[i - 1][j] + nums[i - 1] * multipliers[k]);
      }
      if (j > 0) {
        f[i][j] = Math.max(f[i][j], f[i][j - 1] + nums[n - j] * multipliers[k]);
      }
      if (i + j === m) {
        ans = Math.max(ans, f[i][j]);
      }
    }
  }
  return ans;
}

Solution 2

class Solution:
  def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
    n, m = len(nums), len(multipliers)
    f = [[-inf] * (m + 1) for _ in range(m + 1)]
    f[0][0] = 0
    ans = -inf
    for i in range(m + 1):
      for j in range(m - i + 1):
        k = i + j - 1
        if i > 0:
          f[i][j] = max(f[i][j], f[i - 1][j] + multipliers[k] * nums[i - 1])
        if j > 0:
          f[i][j] = max(f[i][j], f[i][j - 1] + multipliers[k] * nums[n - j])
        if i + j == m:
          ans = max(ans, f[i][j])
    return ans

class Solution {
  public int maximumScore(int[] nums, int[] multipliers) {
    final int inf = 1 << 30;
    int n = nums.length, m = multipliers.length;
    int[][] f = new int[m + 1][m + 1];
    for (int i = 0; i <= m; i++) {
      Arrays.fill(f[i], -inf);
    }
    f[0][0] = 0;
    int ans = -inf;
    for (int i = 0; i <= m; ++i) {
      for (int j = 0; j <= m - i; ++j) {
        int k = i + j - 1;
        if (i > 0) {
          f[i][j] = Math.max(f[i][j], f[i - 1][j] + multipliers[k] * nums[i - 1]);
        }
        if (j > 0) {
          f[i][j] = Math.max(f[i][j], f[i][j - 1] + multipliers[k] * nums[n - j]);
        }
        if (i + j == m) {
          ans = Math.max(ans, f[i][j]);
        }
      }
    }
    return ans;
  }
}

class Solution {
public:
  int maximumScore(vector<int>& nums, vector<int>& multipliers) {
    const int inf = 1 << 30;
    int n = nums.size(), m = multipliers.size();
    vector<vector<int>> f(m + 1, vector<int>(m + 1, -inf));
    f[0][0] = 0;
    int ans = -inf;
    for (int i = 0; i <= m; ++i) {
      for (int j = 0; j <= m - i; ++j) {
        int k = i + j - 1;
        if (i > 0) {
          f[i][j] = max(f[i][j], f[i - 1][j] + multipliers[k] * nums[i - 1]);
        }
        if (j > 0) {
          f[i][j] = max(f[i][j], f[i][j - 1] + multipliers[k] * nums[n - j]);
        }
        if (i + j == m) {
          ans = max(ans, f[i][j]);
        }
      }
    }
    return ans;
  }
};

func maximumScore(nums []int, multipliers []int) int {
  const inf int = 1 << 30
  n, m := len(nums), len(multipliers)
  f := make([][]int, m+1)
  for i := range f {
    f[i] = make([]int, m+1)
    for j := range f {
      f[i][j] = -inf
    }
  }
  f[0][0] = 0
  ans := -inf
  for i := 0; i <= m; i++ {
    for j := 0; j <= m-i; j++ {
      k := i + j - 1
      if i > 0 {
        f[i][j] = max(f[i][j], f[i-1][j]+multipliers[k]*nums[i-1])
      }
      if j > 0 {
        f[i][j] = max(f[i][j], f[i][j-1]+multipliers[k]*nums[n-j])
      }
      if i+j == m {
        ans = max(ans, f[i][j])
      }
    }
  }
  return ans
}