Skip to content

1770. Maximum Score from Performing Multiplication Operations 👍

  • Time: $O(m^2)$
  • Space: $O(m^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
 public:
  int maximumScore(vector<int>& nums, vector<int>& multipliers) {
    vector<vector<int>> mem(multipliers.size(),
                            vector<int>(multipliers.size(), -1));
    return maximumScore(nums, 0, multipliers, 0, mem);
  }

 private:
  // Returns the maximum score of nums[s..e] and multipliers[i].
  int maximumScore(const vector<int>& nums, int s,
                   const vector<int>& multipliers, int i,
                   vector<vector<int>>& mem) {
    if (i == multipliers.size())
      return 0;
    if (mem[s][i] != -1)
      return mem[s][i];

    // The number of nums picked on the start side is s.
    // The number of nums picked on the end side is i - s.
    // So, e = n - (i - s) - 1.
    const int e = nums.size() - (i - s) - 1;
    const int pickStart = nums[s] * multipliers[i] +
                          maximumScore(nums, s + 1, multipliers, i + 1, mem);
    const int pickEnd = nums[e] * multipliers[i] +
                        maximumScore(nums, s, multipliers, i + 1, mem);
    return mem[s][i] = max(pickStart, pickEnd);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
  public int maximumScore(int[] nums, int[] multipliers) {
    Integer[][] mem = new Integer[multipliers.length][multipliers.length];
    return maximumScore(nums, 0, multipliers, 0, mem);
  }

  private int maximumScore(int[] nums, int s, int[] multipliers, int i, Integer[][] mem) {
    if (i == multipliers.length)
      return 0;
    if (mem[s][i] != null)
      return mem[s][i];

    // The number of nums picked on the start side is s.
    // The number of nums picked on the end side is i - s.
    // So, e = n - (i - s) - 1.
    final int e = nums.length - (i - s) - 1;
    final int pickStart = nums[s] * multipliers[i] + //
                          maximumScore(nums, s + 1, multipliers, i + 1, mem);
    final int pickEnd = nums[e] * multipliers[i] + //
                        maximumScore(nums, s, multipliers, i + 1, mem);
    return mem[s][i] = Math.max(pickStart, pickEnd);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
  def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
    @functools.lru_cache(2000)
    def dp(s: int, i: int) -> int:
      """Returns the maximum score of nums[s..e] and multipliers[i]."""
      if i == len(multipliers):
        return 0

      # The number of nums picked on the start side is s.
      # The number of nums picked on the end side is i - s.
      # So, e = n - (i - s) - 1.
      e = len(nums) - (i - s) - 1
      pickStart = nums[s] * multipliers[i] + dp(s + 1, i + 1)
      pickEnd = nums[e] * multipliers[i] + dp(s, i + 1)
      return max(pickStart, pickEnd)

    return dp(0, 0)