Problem

You are given two 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 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.

Source: https://leetcode.com/problems/maximum-score-from-performing-multiplication-operations

Constraints

• n == nums.length
• m == multipliers.length
• 1 <= m <= 10^3
• m <= n <= 10^5
• -1000 <= nums[i], multipliers[i] <= 1000

Asymptotic Complexity

• Time: O(m^2), visits most cells in a 2D table
• Space: O(m^2), requires a square, 2D table

Forward

This is a description for the bottom-up, tabulated approach using dynamic programming. I'm writing this description because building the bottom-up approach was not as intuitive as top-down recursion. However, this problem is worth doing and if you're stuck, maybe this can help you out a bit.

Overview

• We want to create a table where we can build an incremental solution
• Each cell in the table should represent the previous-maximum-value + maximum-current-product
• The maximum-current-product is the product of a multiplier and an optimum LHS or RHS value from nums
• After choosing the LHS or RHS from nums, we cannot reuse that value

Top-Down Behavior

Unless you already see the pattern, lets work through a small problem first. It can be useful to start with a top-down approach:

• nums: [1, 2, 3]
• multipliers: [3, 2, 1]

The formula we'll use for calculating a child value is:

• [parent] + ([multiplier] * [LHS | RHS])

ROOT

• The root value is always: 0

LEVEL 0

• multiplier[0] is: 3
• nums = {1, 2, 3}
• L = 1, R = 3
• A = 0 + (3 x 1) = 3
• B = 0 + (3 x 3) = 9
• If we were building a tree, it would look like this:
  _ _ 0 _ _
_ / _ \ _
3 _ _ _ 9

LEVEL 1

• multiplier[1] is: 2
• Starting with node: A(3)
  • nums = {2, 3}
  • L = 2, R = 3
  • C = 3 + (2 x 2) = 7
  • D = 3 + (2 x 3) = 6
• Starting with node B(9)
  • nums = {1, 2}
  • L = 1, R = 2
  • E = 9 + (2 x 1) = 11
  • F = 9 + (2 x 2) = 13

LEVEL 2

• multiplier[2] is: 1
• Starting with node: C(7)
  • nums = {3}
  • G = 7 + (1 x 3) = 10
• Starting with node D(6)
  • nums = {2}
  • H = 6 + (1 x 2) = 8
• Starting with node E(11)
  • nums = {2}
  • I = 11 + (1 x 2) = 13
• Starting with node F(13)
  • nums = {1}
  • J = 13 + (1 x 1) = 14

SOLUTION

• Return the maximum from the last level {G, H, I, J}: 14

Observations

• multiplier can be indexed by tree depth
• nums should be empty when we get to the last multiplier
• We're starting to see how we might build an incremental solution
• There is some question about how to access and store data without a tree

Tabulation

• To represent the tree in a table, consider the following 2D array:

  0 9 . .
3 . . .
. . . .
. . . .

• Think of it as a tree turned 45 degress counter-clockwise

• The root: 0 has two children: 9 and 3

• You've probably noticed that we can't represent a binary tree this way (due to collisions)

• However, we only care about adding to maximum values

• We can drop suboptimal values as needed, discussed below

Multiplier

• If we continue in this direction, each diagonal is the bottom of a tree level

• As we observed, the tree-level can be used to index the multiplier array

• First multiplier m[0] = 3:

  . 3 . .
3 . . .
. . . .
. . . .

• The second multiplier m[1] is 2:

  . . 2 .
. 2 . .
2 . . .
. . . .

• The third multiplier m[2] is 1:

  . . . 1
. . 1 .
. 1 . .
1 . . .

• The last diagonal is where we need to search for the maximum value

• Note: the rest of the table is unused

  . . . .
. . . X
. . X X
. X X X

Child Nodes

• Starting from A and ending at I, the middle nodes D, G and H will need to determine if they attach to their left or top parent

  . A C F
B D G .
E H . .
I . . .

• For example, D either needs to build upon the A (top) or B (left) solution

• This is how we work around storing a binary tree in the table

• For example, if A=9 and B=3 then D should add its result to A , not B

Implementation

class Solution {
public:
    int maximumScore(vector<int>& nums, vector<int>& multipliers) {
        const auto m = static_cast<int>(multipliers.size());
        const auto n = static_cast<int>(nums.size());
        vector<vector<int>> dp(m + 1, vector<int>(m + 1));
        for (auto z = 0; z < m; ++z) {
            int row{0};
            int col{z + 1};
            while (col >= 0) {
                dp[row][col] = max(
                    (row > 0 ? dp[row - 1][col] + nums[row - 1] * multipliers[z] : INT_MIN),
                    (col > 0 ? dp[row][col - 1] + nums[n - col] * multipliers[z] : INT_MIN));

                --col;
                ++row;
            }
        }

        auto maxScore = INT_MIN;
        for (auto row = 0; row <= m; ++row) {
            maxScore = max(maxScore, dp[row][m - row]);
        }

        return maxScore;
    }
};