Problem Description

You have two integer arrays:

• Array a with exactly 4 elements
• Array b with at least 4 elements

Your task is to select 4 indices from array b: i₀, i₁, i₂, and i₃, where these indices must be in strictly increasing order (i₀ < i₁ < i₂ < i₃).

Once you've selected these 4 indices, your score is calculated as: score = a[0] * b[i₀] + a[1] * b[i₁] + a[2] * b[i₂] + a[3] * b[i₃]

The goal is to find the selection of indices that maximizes this score and return the maximum possible score.

For example, if a = [1, 2, 3, 4] and b = [5, 6, 7, 8, 9], you could choose indices 0, 1, 2, 3 from array b, giving you a score of 1*5 + 2*6 + 3*7 + 4*8 = 70. Or you could choose different indices like 0, 1, 2, 4, giving you 1*5 + 2*6 + 3*7 + 4*9 = 74, and so on. The problem asks you to find the maximum among all possible valid selections.

Intuition

The key insight is that we need to make a series of decisions: for each element in array a, we need to pick a corresponding element from array b, ensuring our picks are in increasing order of indices.

At any point in our decision-making process, we face a choice: should we use the current element from array b or skip it and look for a better option later? This naturally leads to a recursive approach where we explore both possibilities.

Think of it as having two pointers: one for array a (tracking which element we're trying to match) and one for array b (tracking which element we're considering). At each step:

• We can skip the current element in b and move to the next one (keeping the same position in a)
• We can pair the current elements from both arrays and move both pointers forward

Since we need exactly 4 elements from b in increasing order to match with the 4 elements of a, we're essentially finding the optimal subsequence of length 4 from array b that maximizes the dot product with array a.

The recursive nature of this problem becomes clear when we realize that after making a choice at position (i, j), we face a similar but smaller problem at the next positions. This overlapping subproblem structure makes it perfect for dynamic programming with memoization.

The function dfs(i, j) represents: "What's the maximum score I can get if I still need to match elements from position i onwards in array a with elements from position j onwards in array b?" By caching these results, we avoid recalculating the same subproblems multiple times.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution uses a recursive approach with memoization to find the maximum score. Here's how the implementation works:

We define a recursive function dfs(i, j) where:

• i represents the current index in array a (which element we're trying to match)
• j represents the current index in array b (which element we're considering)

The function returns the maximum score achievable starting from these positions.

Base Cases:

1. If j >= len(b): We've exhausted array b. If we've also matched all elements of a (i.e., i >= len(a)), we return 0 as we've successfully formed a valid selection. Otherwise, we return -inf because we can't complete the matching.

2. If i >= len(a): We've successfully matched all elements of array a, so we return 0.

Recursive Cases: For each position (i, j), we have two choices:

• Skip the current element in b: Call dfs(i, j + 1) to consider the next element in b while staying at the same position in a
• Use the current element in b: Calculate a[i] * b[j] and add it to dfs(i + 1, j + 1), which represents matching the current elements and moving forward in both arrays

We take the maximum of these two options: max(dfs(i, j + 1), a[i] * b[j] + dfs(i + 1, j + 1))

Memoization: The @cache decorator automatically memoizes the function results. This prevents redundant calculations when the same (i, j) pair is encountered multiple times through different recursive paths, reducing the time complexity from exponential to polynomial.

Starting Point: The solution begins with dfs(0, 0), which finds the maximum score starting from the beginning of both arrays.

The algorithm essentially explores all valid ways to select 4 indices from array b in increasing order, calculating the score for each valid selection, and returns the maximum among all possibilities.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Given:

• a = [2, 3, 1, 4]
• b = [1, 5, 2, 3, 6]

We need to select 4 indices from b in strictly increasing order to maximize the score.

Starting with dfs(0, 0):

• We're at position 0 in array a (value 2) and position 0 in array b (value 1)
• We have two choices:
  1. Skip b[0]: Call dfs(0, 1) - look for a better match for a[0] starting from b[1]
  2. Use b[0]: Score = 2 × 1 = 2, then call dfs(1, 1) to match remaining elements

Let's trace the path that leads to the optimal solution:

Path to optimal: indices 0, 1, 3, 4 from b

1. dfs(0, 0): Use b[0] → score = 2 × 1 = 2, continue with dfs(1, 1)
2. dfs(1, 1): Use b[1] → score = 3 × 5 = 15, continue with dfs(2, 2)
3. dfs(2, 2): Skip b[2], try dfs(2, 3)
4. dfs(2, 3): Use b[3] → score = 1 × 3 = 3, continue with dfs(3, 4)
5. dfs(3, 4): Use b[4] → score = 4 × 6 = 24, continue with dfs(4, 5)
6. dfs(4, 5): Base case (i ≥ len(a)) → return 0

Total score = 2 + 15 + 3 + 24 = 44

Alternative path explored: indices 1, 2, 3, 4

1. dfs(0, 0): Skip b[0], try dfs(0, 1)
2. dfs(0, 1): Use b[1] → score = 2 × 5 = 10, continue with dfs(1, 2)
3. dfs(1, 2): Use b[2] → score = 3 × 2 = 6, continue with dfs(2, 3)
4. dfs(2, 3): Use b[3] → score = 1 × 3 = 3, continue with dfs(3, 4)
5. dfs(3, 4): Use b[4] → score = 4 × 6 = 24, continue with dfs(4, 5)
6. dfs(4, 5): Base case → return 0

Total score = 10 + 6 + 3 + 24 = 43

The algorithm explores all valid combinations through the recursive calls, using memoization to avoid recalculating identical subproblems. When dfs(2, 3) is called from different paths, for instance, it's only computed once and the cached result is reused.

The maximum score of 44 is returned, corresponding to selecting indices [0, 1, 3, 4] from array b.

Solution Implementation

Time and Space Complexity

The time complexity is O(m × n), where m is the length of array a and n is the length of array b. This is because the recursive function dfs(i, j) explores all possible combinations of indices i (ranging from 0 to m) and j (ranging from 0 to n). Due to the @cache decorator, each unique state (i, j) is computed only once, resulting in at most (m + 1) × (n + 1) different states to compute.

The space complexity is O(m × n). This comes from two sources:

1. The memoization cache stores up to (m + 1) × (n + 1) entries, which is O(m × n) space.
2. The recursion depth in the worst case is O(min(m, n)) for the call stack, but this is dominated by the cache storage.

Therefore, the overall space complexity is O(m × n).

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

Common Pitfalls

1. Integer Overflow with Large Numbers

When dealing with multiplication of potentially large integers, the product a[i] * b[j] could exceed typical integer bounds in some programming languages. While Python handles arbitrary precision integers automatically, this could be problematic in languages like Java or C++.

Solution: In languages with fixed integer sizes, use appropriate data types (e.g., long long in C++ or Long in Java) to handle large products.

2. Incorrect Base Case Handling

A common mistake is not properly handling the base cases, particularly when j >= len(b). The condition return 0 if i >= len(a) else -inf is crucial. Returning 0 when we haven't matched all elements of a would incorrectly suggest a valid solution exists.

Solution: Always return negative infinity (-inf) when we've exhausted array b but still have unmatched elements in array a. This ensures invalid paths are properly rejected when taking the maximum.

3. Off-by-One Errors in Index Boundaries

It's easy to confuse whether to use > or >= when checking array boundaries. Using j > len(b) instead of j >= len(b) would cause an index out of bounds error.

Solution: Remember that array indices are 0-based, so j >= len(b) correctly identifies when we've moved past the last valid index.

4. Forgetting to Clear Cache Between Test Cases

In competitive programming or when running multiple test cases, the @cache decorator persists memoized values between function calls. This can lead to incorrect results if the arrays change between test cases.

Solution: Either:

• Move the cached function definition inside the main function so it's recreated for each test case
• Manually clear the cache using dfs.cache_clear() before each new test case
• Use a dictionary-based memoization that's local to each function call

5. Not Considering Negative Numbers

The algorithm works correctly with negative numbers, but developers might incorrectly assume all values are positive and add unnecessary constraints or optimizations that break with negative values.

Solution: Test with arrays containing negative numbers to ensure the solution handles all cases correctly. The algorithm naturally handles negatives since it explores all possibilities and selects the maximum.