Maximum score using exactly k pairs

Array Dynamic Programming

41.4% acceptance

Mar 16, 2026

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn max_score(nums1: Vec<i32>, nums2: Vec<i32>, k: i32) -> i64 {
    let n = nums1.len();
    let m = nums2.len();
    let k = k as usize;

    // dp[i][j][t] = max score using exactly t pairs from nums1[0..i] and nums2[0..j]
    // Transition: dp[i][j][t] = max(dp[i-1][j][t], dp[i][j-1][t], dp[i-1][j-1][t-1] + nums1[i-1]*nums2[j-1])

    const NEG_INF: i64 = i64::MIN / 2;

    // dp[j][t] with rolling over i
    // We need dp[i][j][t] depending on dp[i-1][j][t], dp[i][j-1][t], dp[i-1][j-1][t-1]
    // Use 2D: prev[j][t] for i-1, curr[j][t] for i

    let mut prev = vec![vec![NEG_INF; k + 1]; m + 1];
    // Base: 0 pairs selected = 0 score
    for j in 0..=m {
      prev[j][0] = 0;
    }

    for i in 1..=n {
      let mut curr = vec![vec![NEG_INF; k + 1]; m + 1];
      curr[0][0] = 0;
      for j in 1..=m {
        for t in 0..=k.min(i).min(j) {
          let mut best = prev[j][t]; // skip nums1[i-1]
          best = best.max(curr[j-1][t]); // skip nums2[j-1]
          if t > 0 {
            let pair_score = nums1[i-1] as i64 * nums2[j-1] as i64;
            if prev[j-1][t-1] != NEG_INF {
              best = best.max(prev[j-1][t-1] + pair_score);
            }
          }
          curr[j][t] = best;
        }
      }
      prev = curr;
    }

    prev[m][k]
  }
}