Maximum Multiplication Score - Video Solutions

Problem Overview: You are given two arrays where one array contains four coefficients and the other contains many values. The task is to choose four increasing indices from the larger array and maximize the total score a[0]*b[i1] + a[1]*b[i2] + a[2]*b[i3] + a[3]*b[i4]. Order must be preserved, so once an index is chosen the next must come after it.

Approach 1: Backtracking Enumeration (Exponential Time)

This approach explores every possible combination of four indices from the second array while maintaining increasing order. A recursive function decides whether to include the current index or skip it. Once four elements are chosen, compute the multiplication score and update the maximum. This brute force technique directly models the problem but examines all combinations, leading to O(n^4) time complexity and O(4) recursion stack space. It works only for very small inputs and mainly helps you understand the structure of the decision tree.

Approach 2: Dynamic Programming (Optimal, O(n))

The key observation: you only need to know the best score after selecting the first k multipliers while scanning the second array from left to right. Define a DP state where dp[k] represents the maximum score after selecting k elements so far. For each value in the second array, update states in reverse order: compute potential contributions for the 4th, 3rd, 2nd, and 1st selections using a[k] * b[i]. Updating backward prevents overwriting states needed for the same iteration. This converts the combinational search into a linear scan with constant states.

The algorithm iterates through the array once and updates four DP states per element. That gives O(n) time complexity and O(1) space. This technique is a classic pattern in dynamic programming: compressing a multi-step decision process into rolling states. The ordered selection constraint is handled naturally because the scan moves left to right through the array. Conceptually, it resembles subsequence DP problems where each step extends the best partial solution.

Recommended for interviews: Start by explaining the brute-force combination idea to demonstrate understanding of the ordered selection constraint. Then transition to the dynamic programming optimization that tracks the best score for each selection stage. Interviewers typically expect the O(n) DP solution with constant space because it shows familiarity with subsequence-style DP state compression.