Skip to content

3836. Maximum Score Using Exactly K Pairs

Description

You are given two integer arrays nums1 and nums2 of lengths n and m respectively, and an integer k.

You must choose exactly k pairs of indices (i1, j1), (i2, j2), ..., (ik, jk) such that:

  • 0 <= i1 < i2 < ... < ik < n
  • 0 <= j1 < j2 < ... < jk < m

For each chosen pair (i, j), you gain a score of nums1[i] * nums2[j].

The total score is the sum of the products of all selected pairs.

Return an integer representing the maximum achievable total score.

 

Example 1:

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

Output: 22

Explanation:

One optimal choice of index pairs is:

  • (i1, j1) = (1, 0) which scores 3 * 4 = 12
  • (i2, j2) = (2, 1) which scores 2 * 5 = 10

This gives a total score of 12 + 10 = 22.

Example 2:

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

Output: 26

Explanation:

One optimal choice of index pairs is:

  • (i1, j1) = (0, 0) which scores -2 * -3 = 6
  • (i2, j2) = (2, 1) which scores 5 * 4 = 20

The total score is 6 + 20 = 26.

Example 3:

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

Output: -7

Explanation:

The optimal choice of index pairs is:

  • (i1, j1) = (0, 0) which scores -3 * 1 = -3
  • (i2, j2) = (1, 1) which scores -2 * 2 = -4

The total score is -3 + (-4) = -7.

 

Constraints:

  • 1 <= n == nums1.length <= 100
  • 1 <= m == nums2.length <= 100
  • -106 <= nums1[i], nums2[i] <= 106
  • 1 <= k <= min(n, m)

Solutions

Solution 1: Dynamic Programming

Thinking

Pick \(k\) index-increasing pairs from two arrays and maximize the sum of products. \(n,m \le 100\) and \(k \le \min(n,m)\) fit a 3-D DP.

A pair consumes one element from each side and cannot go backwards. The choices are skip \(nums1\), skip \(nums2\), or pair both.

Let \(f[i][j][k]\) be the best score using the two prefixes and exactly \(k\) pairs, with those three transitions.

The empty prefixes with zero pairs score \(0\); other states start at \(-\infty\). The answer is \(f[n][m][K]\).

We denote the lengths of arrays \(\textit{nums1}\) and \(\textit{nums2}\) as \(n\) and \(m\) respectively, and denote \(k\) in the problem as \(K\).

We define a three-dimensional array \(f\), where \(f[i][j][k]\) represents the maximum score of selecting exactly \(k\) index pairs from the first \(i\) elements of \(\textit{nums1}\) and the first \(j\) elements of \(\textit{nums2}\). Initially, \(f[0][0][0] = 0\), and all other values of \(f[i][j][k]\) are negative infinity.

We can calculate \(f[i][j][k]\) through the following state transition equation:

\[ f[i][j][k] = \max\begin{cases} f[i-1][j][k], \\ f[i][j-1][k], \\ f[i-1][j-1][k-1] + nums1[i-1] * nums2[j-1] \end{cases} \]

The first case represents not selecting the \(i\)-th element of \(\textit{nums1}\), the second case represents not selecting the \(j\)-th element of \(\textit{nums2}\), and the third case represents selecting the \(i\)-th element of \(\textit{nums1}\) and the \(j\)-th element of \(\textit{nums2}\) as a pair of indices.

Finally, we need to return \(f[n][m][K]\).

The time complexity is \(O(m \times n \times K)\) and the space complexity is \(O(m \times n \times K)\), where \(n\) and \(m\) are the lengths of arrays \(\textit{nums1}\) and \(\textit{nums2}\) respectively, and \(K\) is \(k\) in the problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def maxScore(self, nums1: List[int], nums2: List[int], K: int) -> int:
        n, m = len(nums1), len(nums2)
        f = [[[-inf] * (K + 1) for _ in range(m + 1)] for _ in range(n + 1)]
        f[0][0][0] = 0
        for i in range(n + 1):
            for j in range(m + 1):
                for k in range(K + 1):
                    if i > 0:
                        f[i][j][k] = max(f[i][j][k], f[i - 1][j][k])
                    if j > 0:
                        f[i][j][k] = max(f[i][j][k], f[i][j - 1][k])
                    if i > 0 and j > 0 and k > 0:
                        f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][k - 1] + nums1[i - 1] * nums2[j - 1])
        return f[n][m][K]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public long maxScore(int[] nums1, int[] nums2, int K) {
        int n = nums1.length, m = nums2.length;
        long NEG = Long.MIN_VALUE / 4;
        long[][][] f = new long[n + 1][m + 1][K + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                Arrays.fill(f[i][j], NEG);
            }
        }
        f[0][0][0] = 0;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= K; k++) {
                    if (i > 0) {
                        f[i][j][k] = Math.max(f[i][j][k], f[i - 1][j][k]);
                    }
                    if (j > 0) {
                        f[i][j][k] = Math.max(f[i][j][k], f[i][j - 1][k]);
                    }
                    if (i > 0 && j > 0 && k > 0) {
                        f[i][j][k] = Math.max(f[i][j][k],
                            f[i - 1][j - 1][k - 1] + (long) nums1[i - 1] * nums2[j - 1]);
                    }
                }
            }
        }
        return f[n][m][K];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    long long maxScore(vector<int>& nums1, vector<int>& nums2, int K) {
        int n = nums1.size(), m = nums2.size();
        long long NEG = LLONG_MIN / 4;
        vector f(n + 1, vector(m + 1, vector<long long>(K + 1, NEG)));
        f[0][0][0] = 0;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= K; k++) {
                    if (i > 0) {
                        f[i][j][k] = max(f[i][j][k], f[i - 1][j][k]);
                    }
                    if (j > 0) {
                        f[i][j][k] = max(f[i][j][k], f[i][j - 1][k]);
                    }
                    if (i > 0 && j > 0 && k > 0) {
                        f[i][j][k] = max(
                            f[i][j][k],
                            f[i - 1][j - 1][k - 1] + 1LL * nums1[i - 1] * nums2[j - 1]);
                    }
                }
            }
        }
        return f[n][m][K];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
func maxScore(nums1 []int, nums2 []int, K int) int64 {
    n, m := len(nums1), len(nums2)
    NEG := int64(math.MinInt64 / 4)
    f := make([][][]int64, n+1)
    for i := 0; i <= n; i++ {
        f[i] = make([][]int64, m+1)
        for j := 0; j <= m; j++ {
            f[i][j] = make([]int64, K+1)
            for k := 0; k <= K; k++ {
                f[i][j][k] = NEG
            }
        }
    }
    f[0][0][0] = 0
    for i := 0; i <= n; i++ {
        for j := 0; j <= m; j++ {
            for k := 0; k <= K; k++ {
                if i > 0 {
                    f[i][j][k] = max(f[i][j][k], f[i-1][j][k])
                }
                if j > 0 {
                    f[i][j][k] = max(f[i][j][k], f[i][j-1][k])
                }
                if i > 0 && j > 0 && k > 0 {
                    f[i][j][k] = max(
                        f[i][j][k],
                        f[i-1][j-1][k-1]+int64(nums1[i-1])*int64(nums2[j-1]),
                    )
                }
            }
        }
    }
    return f[n][m][K]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function maxScore(nums1: number[], nums2: number[], K: number): number {
    const n = nums1.length,
        m = nums2.length;
    const NEG = -1e18;
    const f = Array.from({ length: n + 1 }, () =>
        Array.from({ length: m + 1 }, () => Array(K + 1).fill(NEG)),
    );
    f[0][0][0] = 0;
    for (let i = 0; i <= n; i++) {
        for (let j = 0; j <= m; j++) {
            for (let k = 0; k <= K; k++) {
                if (i > 0) {
                    f[i][j][k] = Math.max(f[i][j][k], f[i - 1][j][k]);
                }
                if (j > 0) {
                    f[i][j][k] = Math.max(f[i][j][k], f[i][j - 1][k]);
                }
                if (i > 0 && j > 0 && k > 0) {
                    f[i][j][k] = Math.max(
                        f[i][j][k],
                        f[i - 1][j - 1][k - 1] + nums1[i - 1] * nums2[j - 1],
                    );
                }
            }
        }
    }
    return f[n][m][K];
}

Comments