3290. Maximum Multiplication Score

Problem Description

You are given an integer array a of size 4 and another integer array b of size at least 4.

You need to choose 4 indices i0, i1, i2, and i3 from the array b such that i0 < i1 < i2 < i3. Your score will be equal to the value a[0] * b[i0] + a[1] * b[i1] + a[2] * b[i2] + a[3] * b[i3].

Return the maximum score you can achieve.

Intuition

The problem involves selecting four elements from array b in a strictly increasing order of indices to maximize the given scoring function using fixed weights from array a. This problem can be considered as an optimization problem where we need to cleverly choose the indices in b to maximize a sum.

The approach to solving this involves dynamic programming with memoization where the function dfs(i, j) is used to determine the maximum score possible starting from the i-th element of array a and from the j-th element of array b.

The main idea is that for each element in array a, we scan through possible elements in array b that haven't been used yet to generate the highest score possible and use a recursive strategy to explore subsequent selections. Here's how it works:

If array b is fully scanned (j ≥ len(b)), the score is zero if all elements in a have been used; otherwise, return negative infinity to denote this path is invalid.
If array a is fully traversed (i ≥ len(a)), return 0 since there are no more elements in a to match with in b.
Otherwise, for the current pair (i, j), determine whether to skip the j-th element in b or select it:
- By skipping element b[j], the problem reduces to dfs(i, j + 1).
- By selecting b[j], and thus getting contribution a[i] * b[j], the problem then reduces to finding the rest of the elements by calling dfs(i + 1, j + 1).

Taking the maximum of these two choices at every step helps to ensure that the maximum score achievable from any point in the arrays is computed. Using memoization helps cache results to avoid recalculating already solved subproblems, making the algorithm efficient.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution employs dynamic programming with memoization to maximize the score of selecting indices from b based on the fixed scoring weights from a. The core idea revolves around defining a recursive function dfs(i, j) which calculates the maximum score possible by choosing indices from the current positions in arrays a and b.

Steps Involved:

Define the Recursive Function:
The function dfs(i, j) denotes the maximum score starting from the i-th element of a and the j-th element of b.
Base Cases:
- If j >= len(b): The entire b array has been traversed. If all elements of a are covered, return 0 since no more scores can be added. Otherwise, returning -inf ensures that this path is not valid since it didn't use all elements of a.
- If i >= len(a): All elements of a have been used, thus return 0 because no further contributions are possible.
Recursive Choices:
- Skip the current index j in b: This corresponds to calling dfs(i, j + 1), continuing with the next index in b without using b[j].
- Include the current index j in b: Score a[i] * b[j] and add this to the result of dfs(i + 1, j + 1), which processes the next elements of both a and b.
Memoization:
- The @cache decorator is used to cache results of dfs(i, j) calls. This avoids redundant calculations, optimizing the overall execution time.
Final Call:
- The result of the problem is given by dfs(0, 0), which starts the process from the first positions in both a and b, exploring all possible valid selections to yield the maximum score.

The described algorithm has a time complexity driven by the double loop over both arrays, mitigated by memoization to ensure each subproblem is solved once. This effectively leverages the benefits of recursive exploration without unnecessary recomputations.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider the following example to understand how the solution works:

Example:

Array a: [2, 3, 5, 7]
Array b: [1, 2, 3, 4, 5, 6]

Task: Select 4 indices i0 < i1 < i2 < i3 from b to maximize the score a[0] * b[i0] + a[1] * b[i1] + a[2] * b[i2] + a[3] * b[i3].

Step-by-Step Solution Approach:

Define the Recursive Function:
- We define dfs(i, j) where i is the current index in a and j is the current index in b.
Base Cases:
- If j >= len(b), return 0 if i >= len(a), otherwise -inf.
- If i >= len(a), return 0.
Recursive Choices:
- Skip b[j]: Call dfs(i, j + 1).
- Include b[j]: Compute score a[i] * b[j], then call dfs(i + 1, j + 1) and add the result.
Memoization:
- Use memoization to avoid recalculating already explored subproblems.
Start the Calculation:
- Call dfs(0, 0) to start maximizing the score from the beginning of both arrays.

Detailed Exploration for Example:

Starting with dfs(0, 0), consider:
- Skip b[0] (=1): Calculate dfs(0, 1).
- Include b[0]: Calculate score 2 * 1 = 2 and add result of dfs(1, 1).
Next, in dfs(1, 1), consider:
- Skip b[1] (=2): Calculate dfs(1, 2).
- Include b[1]: Calculate score 3 * 2 = 6 and add result of dfs(2, 2).
This recursive process continues through all valid paths, considering each combination of skipping or including an element.
Finally, once dfs has traversed all potential configurations, we will end up with the maximum score possible from dfs(0, 0).

For the given example, the selected indices might end up selecting elements from b like [2, 3, 5, 6] for the maximum score computation:

Calculation: 2 * 2 + 3 * 3 + 5 * 5 + 7 * 6 = 4 + 9 + 25 + 42 = 80.

Thus, the maximum score for this particular configuration would be 80.

By evaluating all valid configurations using dynamic programming with memoization, the algorithm finds the optimal indices maximizing the score.

Solution Implementation

1from typing import List
2from functools import lru_cache
3
4class Solution:
5    def maxScore(self, a: List[int], b: List[int]) -> int:
6        # Decorate the recursive DFS function with LRU cache to optimize repeated calls
7        @lru_cache(None)
8        def dfs(i: int, j: int) -> int:
9            # Base case: if pointer for list b exceeds length, return 0 or negative infinity based on list a
10            if j >= len(b):
11                return 0 if i >= len(a) else float('-inf')
12            # Base case: if pointer for list a exceeds length, return 0 as no more elements can be chosen from a
13            if i >= len(a):
14                return 0
15            # Choose the maximum score between skipping b[j] or using both a[i] and b[j] plus `dfs` for the next elements
16            return max(dfs(i, j + 1), a[i] * b[j] + dfs(i + 1, j + 1))
17
18        # Start the depth-first search from the initial indices (0, 0)
19        return dfs(0, 0)
20

1class Solution {
2    private Long[][] memoizationTable;  // Memoization table to store calculated results
3    private int[] arrayA;               // Array 'a' to be used in calculations
4    private int[] arrayB;               // Array 'b' to be used in calculations
5
6    // Method to calculate the maximum score
7    public long maxScore(int[] a, int[] b) {
8        // Initialize the memoization table with dimensions corresponding to input arrays
9        memoizationTable = new Long[a.length][b.length];
10        this.arrayA = a;  // Assign array 'a' to the class variable
11        this.arrayB = b;  // Assign array 'b' to the class variable
12        // Start recursive DFS from the first index of both arrays
13        return dfs(0, 0);
14    }
15
16    // Depth-first search method with memoization
17    private long dfs(int indexA, int indexB) {
18        // Base case: If we've exhausted all elements of array 'b'
19        if (indexB >= arrayB.length) {
20            // Check if all elements of array 'a' are also exhausted
21            return indexA >= arrayA.length ? 0 : Long.MIN_VALUE / 2;
22        }
23        // Base case: If all elements of array 'a' are used, no more scores can be added
24        if (indexA >= arrayA.length) {
25            return 0;
26        }
27        // If the result is already computed, retrieve it from the memoization table
28        if (memoizationTable[indexA][indexB] != null) {
29            return memoizationTable[indexA][indexB];
30        }
31        // Calculate maximum score either by skipping the current element of 'b'
32        // or by taking it along with 'a' and moving to the next elements
33        long skipCurrentB = dfs(indexA, indexB + 1);
34        long takeCurrentABPair = 1L * arrayA[indexA] * arrayB[indexB] + dfs(indexA + 1, indexB + 1);
35        // Store the result in the memoization table and return it
36        return memoizationTable[indexA][indexB] = Math.max(skipCurrentB, takeCurrentABPair);
37    }
38}
39

1class Solution {
2public:
3    long long maxScore(vector<int>& a, vector<int>& b) {
4        // Get the sizes of vectors a and b
5        int m = a.size();
6        int n = b.size();
7      
8        // Initialize a 2D array to store intermediate results, set all values to -1
9        long long f[m][n];
10        memset(f, -1, sizeof(f));
11      
12        // Define a lambda function to perform the dynamic programming via depth-first search
13        auto dfs = [&](auto&& dfsRef, int i, int j) -> long long {
14            // Base case: if j is out of bounds for vector b, return a suitable condition
15            if (j >= n) {
16                return i >= m ? 0 : LLONG_MIN / 2;  // Out of bounds i means invalid path
17            }
18            // If i is out of bounds for vector a, return 0 since no further elements
19            if (i >= m) {
20                return 0;
21            }
22            // Return already computed value to avoid redundant calculations
23            if (f[i][j] != -1) {
24                return f[i][j];
25            }
26          
27            // Compute the maximum score by choosing or skipping the current element
28            f[i][j] = max(
29                dfsRef(dfsRef, i, j + 1),  // Skip the current element in b[j]
30                1LL * a[i] * b[j] + dfsRef(dfsRef, i + 1, j + 1)  // Choose the current elements from both a[i] and b[j]
31            );
32          
33            return f[i][j];
34        };
35
36        // Start the computation from the beginning of both arrays
37        return dfs(dfs, 0, 0);
38    }
39};
40

1// The maxScore function calculates the maximum score by maximizing the product
2// of the elements from two arrays, a and b. Dynamic programming is used to store
3// and reuse intermediate results.
4
5function maxScore(a: number[], b: number[]): number {
6    // Get the lengths of arrays a and b.
7    const [m, n] = [a.length, b.length];
8
9    // Initialize a 2D array to store intermediate results, using -1 as the default value.
10    const dp: number[][] = Array.from({ length: m }, () => Array(n).fill(-1));
11
12    // Recursive function with memoization to compute the maximum score.
13    const dfs = (i: number, j: number): number => {
14        // If index j reaches or exceeds the length of b, check index i.
15        if (j >= n) {
16            // Return 0 if all elements are processed, otherwise negative infinity to avoid invalid states.
17            return i >= m ? 0 : -Infinity;
18        }
19        // If index i reaches or exceeds the length of a, return 0 as no more elements can be used from a.
20        if (i >= m) {
21            return 0;
22        }
23        // If the result for this state (i, j) is already computed, return it.
24        if (dp[i][j] !== -1) {
25            return dp[i][j];
26        }
27      
28        // Calculate the maximum score by either:
29        // 1. Skipping the current element from b and moving to the next (i, j+1).
30        // 2. Taking the current elements a[i] and b[j], adding their product to the result and moving to the next elements (i+1, j+1).
31        const skipElement = dfs(i, j + 1);
32        const takeElement = a[i] * b[j] + dfs(i + 1, j + 1);
33      
34        // Memorize and return the maximum score for the current state (i, j).
35        return (dp[i][j] = Math.max(skipElement, takeElement));
36    };
37
38    // Start the recursion from index (0, 0) and return the maximum score.
39    return dfs(0, 0);
40}
41

Time and Space Complexity

The time complexity of the code is O(m \times n). This is because the dfs function is called with every combination of indices i and j, where i varies over the length of a and j varies over the length of b. Since there are m choices for i and n choices for j, the total number of states is m \times n.

The space complexity of the code is also O(m \times n). This complexity arises primarily from the use of the @cache decorator, which stores the results of each (i, j) computation. The maximum number of these stored results is equal to the number of distinct (i, j) pairs, which is m \times n.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

The three-steps of Depth First Search are:

Identify states;
Draw the state-space tree;
DFS on the state-space tree.

True

False

I don’t know