We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Multiplication Score

Number: 3518

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given two integer arrays a (of size 4) and b (of size at least 4), choose 4 indices i0, i1, i2, and i3 from b (with i0 < i1 < i2 < i3) so that the score computed as:
  a[0] * b[i0] + a[1] * b[i1] + a[2] * b[i2] + a[3] * b[i3]
is maximized. Return the maximum score achievable.

Key Insights

  • The array a has a fixed size (4) and the order of selection in b matters (increasing indices).
  • A dynamic programming (DP) approach can be applied where we progressively pick elements from b.
  • We use DP to maintain the best achievable score after choosing k elements (k = 0..4), updating in order.
  • The DP state update is done in reverse order for each element in b to avoid overwriting states needed for the next update.
  • Time complexity is O(n) since we iterate through b only once, and there are only 4 stages.

Space and Time Complexity

Time Complexity: O(n), where n is the length of b
Space Complexity: O(1), as we use only a fixed-size DP array with 5 elements

Solution

We solve the problem using dynamic programming. We maintain a DP array dp of size 5 (indexes 0 to 4) where dp[k] represents the maximum achievable score by selecting k elements from b corresponding to the first k elements of a. We initialize dp[0] = 0 (no selections gives 0 score) and dp[1..4] with very small numbers (e.g., negative infinity) to indicate unachievable states initially.

Then, for each element b[i] in b, we update the dp array in reverse order—from dp[4] down to dp[1]. The reason for reverse iteration is to ensure that when calculating dp[k] we use the dp[k-1] value from the same iteration round (from previously considered elements only). The state transition is:

  dp[k] = max(dp[k], dp[k-1] + a[k-1] * b[i])

After processing all elements, dp[4] will hold the maximum achievable score. This approach efficiently ensures the order requirement on b and correctly pairs with the fixed order in a.

Code Solutions

# Python solution using dynamic programming

def maximumMultiplicationScore(a, b):
    # Number of multiplications to be performed (always 4)
    k_num = 4
    # Initialize dp with negative infinity for unreachable states except dp[0]=0
    dp = [0] + [-float('inf')] * k_num
    
    # Iterate through each number in b
    for num in b:
        # Update dp values in reverse order from 4 down to 1
        for k in range(k_num, 0, -1):
            # Update dp[k] by considering the selection of current num.
            dp[k] = max(dp[k], dp[k-1] + a[k-1] * num)
    # The answer is dp[4], representing 4 selections.
    return dp[k_num]

# Example usage:
a = [3, 2, 5, 6]
b = [2, -6, 4, -5, -3, 2, -7]
print(maximumMultiplicationScore(a, b))  # Expected output: 26
← Back to All Questions