LeetCode Problem 3836

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming

Solution

LeetCode 3836 - Maximum Score Using Exactly K Pairs

Problem Understanding

We are given two arrays, nums1 of length n and nums2 of length m, along with an integer k.

Our goal is to choose exactly k pairs of indices:

$$(i_1, j_1), (i_2, j_2), \dots, (i_k, j_k)$$

such that:

$$i_1 < i_2 < \dots < i_k$$

and

$$j_1 < j_2 < \dots < j_k$$

For every chosen pair (i, j), we gain a score equal to:

$$nums1[i] \times nums2[j]$$

The final score is the sum of the products of all selected pairs, and we must maximize this total.

The ordering constraints are extremely important. We are not free to pair arbitrary elements. Once we choose a pair (i, j), every future chosen pair must use larger indices in both arrays. This means the selected pairs form an increasing sequence in both arrays.

The constraints are:

• n, m ≤ 100
• k ≤ min(n, m)
• Values can be as large as 10^6 or as small as -10^6

Because values may be negative, positive, or zero, greedy strategies become unreliable. Sometimes pairing two negative numbers produces a large positive contribution. Sometimes we are forced to include negative products because exactly k pairs must be selected.

Important edge cases include:

• All products are negative.
• Arrays contain both large positive and large negative values.
• k = 1.
• k = min(n, m).
• Multiple valid increasing pair sequences exist.
• We must select exactly k pairs, not at most k.

These observations strongly suggest a dynamic programming solution.

Approaches

Brute Force

A brute force approach would enumerate every increasing subsequence of length k from nums1 and every increasing subsequence of length k from nums2. Then it would pair them position by position and compute the resulting score.

This works because every valid solution corresponds to choosing:

• k increasing indices from nums1
• k increasing indices from nums2

and matching them in order.

Unfortunately, the number of possibilities is enormous:

$$\binom{n}{k}\times \binom{m}{k}$$

Even for moderate values, this becomes completely infeasible.

Key Insight

The ordering constraints create a structure very similar to sequence alignment problems.

Suppose we are currently considering prefixes:

• nums1[0..i-1]
• nums2[0..j-1]

and we still need to know the best score obtainable using exactly t pairs.

At position (i, j) there are only three meaningful choices:

1. Skip nums1[i-1].
2. Skip nums2[j-1].
3. Match nums1[i-1] with nums2[j-1].

If we match them, then the previous part of the solution must come from:

$$(i-1, j-1, t-1)$$

This naturally leads to dynamic programming over prefixes and number of pairs selected.

Because n and m are only 100, a DP with state (i, j, t) is easily feasible.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	$O\left(\binom{n}{k}\binom{m}{k}\right)$	Exponential	Enumerates all valid index selections
Optimal DP	$O(nmk)$	$O(nmk)$	Prefix DP with match and skip transitions

Algorithm Walkthrough

Let:

$$dp[i][j][t]$$

represent the maximum score obtainable using:

• first i elements of nums1
• first j elements of nums2
• exactly t chosen pairs

1. Initialize the DP table

Create a 3D DP table filled with negative infinity.

Negative infinity is necessary because scores may legitimately be negative. Using zero would incorrectly allow impossible states to contribute.

Set:

dp[0][0][0] = 0

since using no elements and selecting zero pairs yields score zero.

2. Process prefixes

Iterate through all:

• i = 0..n
• j = 0..m
• t = 0..k

Each state represents a completed solution on prefixes.

3. Skip an element from nums1

If i < n, propagate:

dp[i+1][j][t]

from:

dp[i][j][t]

This means we ignore nums1[i].

4. Skip an element from nums2

If j < m, propagate:

dp[i][j+1][t]

from:

dp[i][j][t]

This means we ignore nums2[j].

5. Match the current elements

If:

i < n
j < m
t < k

we may pair:

nums1[i] with nums2[j]

The new score becomes:

dp[i][j][t] + nums1[i] * nums2[j]

and updates:

dp[i+1][j+1][t+1]

6. Continue until all states are processed

The answer is:

dp[n][m][k]

which represents using the entire arrays while selecting exactly k pairs.

Why it works

For every state (i, j, t), the DP stores the best possible score using the corresponding prefixes and exactly t matches.

Any optimal solution for prefixes must end in exactly one of three ways:

• the last considered element of nums1 is skipped,
• the last considered element of nums2 is skipped,
• the two elements are matched together.

These are the only possibilities, and the DP explicitly evaluates all of them. Since every transition preserves optimality and every valid solution can be decomposed into smaller prefix solutions, the DP explores all valid increasing pair sequences and returns the maximum possible score.

Python Solution

from typing import List

class Solution:
    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
        n = len(nums1)
        m = len(nums2)

        NEG_INF = float("-inf")

        dp = [[[NEG_INF] * (k + 1) for _ in range(m + 1)] for _ in range(n + 1)]
        dp[0][0][0] = 0

        for i in range(n + 1):
            for j in range(m + 1):
                for t in range(k + 1):
                    cur = dp[i][j][t]

                    if cur == NEG_INF:
                        continue

                    if i < n:
                        dp[i + 1][j][t] = max(
                            dp[i + 1][j][t],
                            cur
                        )

                    if j < m:
                        dp[i][j + 1][t] = max(
                            dp[i][j + 1][t],
                            cur
                        )

                    if i < n and j < m and t < k:
                        dp[i + 1][j + 1][t + 1] = max(
                            dp[i + 1][j + 1][t + 1],
                            cur + nums1[i] * nums2[j]
                        )

        return int(dp[n][m][k])

The implementation directly follows the DP formulation.

The table dp[i][j][t] stores the best score achievable using the first i elements of nums1, the first j elements of nums2, and exactly t matches.

For every reachable state, we consider the three valid transitions. Skipping an element from either array preserves the number of chosen pairs, while matching the current elements increases the pair count by one and adds the product to the score.

Impossible states remain at negative infinity, ensuring they never influence valid computations. After processing all prefixes, dp[n][m][k] contains the optimal answer.

Go Solution

func maxScore(nums1 []int, nums2 []int, k int) int64 {
	n := len(nums1)
	m := len(nums2)

	const NEG_INF int64 = -1 << 60

	dp := make([][][]int64, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = make([][]int64, m+1)
		for j := 0; j <= m; j++ {
			dp[i][j] = make([]int64, k+1)
			for t := 0; t <= k; t++ {
				dp[i][j][t] = NEG_INF
			}
		}
	}

	dp[0][0][0] = 0

	for i := 0; i <= n; i++ {
		for j := 0; j <= m; j++ {
			for t := 0; t <= k; t++ {
				cur := dp[i][j][t]

				if cur == NEG_INF {
					continue
				}

				if i < n {
					if cur > dp[i+1][j][t] {
						dp[i+1][j][t] = cur
					}
				}

				if j < m {
					if cur > dp[i][j+1][t] {
						dp[i][j+1][t] = cur
					}
				}

				if i < n && j < m && t < k {
					candidate := cur + int64(nums1[i])*int64(nums2[j])

					if candidate > dp[i+1][j+1][t+1] {
						dp[i+1][j+1][t+1] = candidate
					}
				}
			}
		}
	}

	return dp[n][m][k]
}

The Go implementation is nearly identical to the Python version. The main difference is that all DP values use int64 because products can reach approximately 10^12, and summing up to 100 such products can exceed 32 bit integer limits. A large negative sentinel value is used instead of negative infinity.

Worked Examples

Example 1

nums1 = [1, 3, 2]
nums2 = [4, 5, 1]
k = 2

The most important match transitions are:

Pair Chosen	Added Score	Total
(1,0) => 3×4	12	12
(2,1) => 2×5	10	22

The DP explores alternatives such as:

Matched Pairs	Score
(0,0),(1,1)	1×4 + 3×5 = 19
(0,1),(1,2)	1×5 + 3×1 = 8
(1,0),(2,1)	3×4 + 2×5 = 22

Maximum score:

22

Example 2

nums1 = [-2,0,5]
nums2 = [-3,4,-1,2]
k = 2

Key DP choices:

Pair	Product
(-2) × (-3)	6
5 × 4	20

Total:

6 + 20 = 26

Alternative combinations produce smaller values.

Thus:

26

is optimal.

Example 3

nums1 = [-3,-2]
nums2 = [1,2]
k = 2

Since exactly two pairs are required, every element must be used.

Pair	Product
-3 × 1	-3
-2 × 2	-4

Total:

-7

The DP correctly keeps negative states instead of replacing them with zero, which is crucial for correctness.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(nmk)	Every state (i,j,t) is processed once
Space	O(nmk)	DP table stores all states

There are (n + 1)(m + 1)(k + 1) states. Each state performs only a constant number of transitions, giving a total running time of O(nmk). The DP table itself dominates memory usage, resulting in O(nmk) space complexity.

Test Cases

sol = Solution()

assert sol.maxScore([1, 3, 2], [4, 5, 1], 2) == 22  # example 1

assert sol.maxScore([-2, 0, 5], [-3, 4, -1, 2], 2) == 26  # example 2

assert sol.maxScore([-3, -2], [1, 2], 2) == -7  # example 3

assert sol.maxScore([5], [7], 1) == 35  # smallest valid input

assert sol.maxScore([-5], [7], 1) == -35  # single negative product

assert sol.maxScore([1, 2, 3], [4, 5, 6], 1) == 18  # best single pair

assert sol.maxScore([-1, -2], [-3, -4], 2) == 11  # all negative values

assert sol.maxScore([0, 0, 0], [1, 2, 3], 2) == 0  # all products zero

assert sol.maxScore([10, -10], [-10, 10], 1) == 100  # choose best sign combination

assert sol.maxScore([1, 2, 3], [4, 5, 6], 3) == 32  # must use all pairs

assert sol.maxScore([1000000], [1000000], 1) == 1000000000000  # large values

assert sol.maxScore([1, -100, 2], [1, -100, 2], 2) == 10001  # skip strategically

Test Summary

Test	Why
Example 1	Basic positive values
Example 2	Mix of negative and positive values
Example 3	All selected products are negative
Single element arrays	Minimum input size
Single negative product	Negative answer handling
k = 1	Best individual match
All negatives	Positive result from negative pairs
All zeros	Zero score handling
Mixed signs	Chooses best product
k = min(n,m)	Forced use of all positions
Large values	Overflow safety
Strategic skipping	Validates DP transitions

Edge Cases

All Scores Are Negative

A common bug is initializing DP states with zero and treating unreachable states as zero. When all valid solutions produce negative scores, this incorrectly allows the algorithm to return zero instead of the true optimum. The implementation uses negative infinity for unreachable states, ensuring negative answers are preserved correctly.

Exactly K Pairs Must Be Chosen

Many sequence matching problems allow selecting any number of matches. This problem requires exactly k pairs. A solution that tracks only the best score for prefixes could accidentally stop early after selecting fewer than k pairs. The DP explicitly includes t, the number of chosen pairs, so the final answer is taken only from states with exactly k matches.

Large Positive and Negative Values

Array values may reach ±10^6. A single product can therefore reach 10^12, and up to 100 products may be summed. Using 32 bit integers would overflow. The Go solution uses int64, and Python's arbitrary precision integers naturally handle these values safely.

K Equals Min(N, M)

When k equals the length of the shorter array, there is very little freedom in the matching process. Some implementations accidentally skip too many elements and become unable to complete the required number of matches. Because the DP tracks the exact match count and explores all valid prefix transitions, it correctly handles these tightly constrained situations.