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) {
    // dp[s][i] := max score of nums[s..e] and multipliers[i],
    dp.resize(multipliers.size(), vector<int>(multipliers.size(), -1));
    return maximumScore(nums, 0, multipliers, 0);
  }

 private:
  vector<vector<int>> dp;

  int maximumScore(const vector<int>& nums, int s,
                   const vector<int>& multipliers, int i) {
    if (i == multipliers.size())
      return 0;
    if (dp[s][i] != -1)
      return dp[s][i];

    // # of nums picked on the start side = s,
    // # of nums picked on the end side = 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);
    const int pickEnd = nums[e] * multipliers[i] +
                        maximumScore(nums, s, multipliers, i + 1);
    return dp[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
24
class Solution {
  public int maximumScore(int[] nums, int[] multipliers) {
    // dp[s][i] := max score of nums[s..e] and multipliers[i],
    dp = new Integer[multipliers.length][multipliers.length];
    return maximumScore(nums, 0, multipliers, 0);
  }

  private Integer[][] dp;

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

    // # of nums picked on the start side = s,
    // # of nums picked on the end side = 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);
    final int pickEnd = nums[e] * multipliers[i] + maximumScore(nums, s, multipliers, i + 1);
    return dp[s][i] = Math.max(pickStart, pickEnd);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
    @lru_cache(2000)
    def dp(s, i):
      if i == len(multipliers):
        return 0

      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)
Back to top