Maximum Score Using Exactly K Pairs - Video Solutions

Problem Overview: You are given an array and must form exactly k disjoint pairs. Each pair contributes a score based on the two selected elements. The goal is to maximize the total score while ensuring every element is used at most once.

Approach 1: Brute Force Pair Enumeration (Exponential Time, O(n^(2k)) time, O(k) space)

The most direct strategy tries every possible way to choose k disjoint pairs. You recursively pick two unused elements, add their score, and continue forming the remaining pairs. This guarantees the optimal answer because every configuration is explored. However, the number of pair combinations grows extremely fast as n increases, making this approach impractical beyond small inputs. It is mainly useful for understanding the search space before optimizing.

Approach 2: Dynamic Programming with Prefix Decisions (O(n² · k) time, O(n · k) space)

The efficient solution uses dynamic programming to avoid recomputing overlapping subproblems. First process the array from left to right and define dp[i][p] as the maximum score achievable using the first i elements while forming exactly p pairs. For each position i, you have two choices: skip the element (carry forward dp[i-1][p]) or pair it with a previous element j. If you pair j and i, add their pair score and transition from dp[j-1][p-1]. Iterating over possible partners ensures all valid pairings are considered while maintaining disjoint usage of elements.

This DP effectively converts an exponential pairing problem into a structured state transition. The outer loop iterates through the array, the inner loop checks potential pairing partners, and the pair count dimension ensures exactly k pairs are formed. Because states reuse previously computed results, the total complexity becomes manageable even for large inputs.

Recommended for interviews: Start by explaining the brute force pairing idea to demonstrate understanding of the constraints and why the search space explodes. Then move to the dynamic programming formulation with dp[i][p]. Interviewers typically expect the DP optimization because it shows you can convert a combinatorial pairing problem into a structured state transition with clear time and space bounds.