Maximum multiplication score

Array Dynamic Programming

41.3% acceptance

Feb 25, 2026

188

You are given an integer array a of size 4 and another integer array b of size at least 4. You need to choose 4 indices i0 < i1 < i2 < i3 from the array b such that your score = a[0]*b[i0] + a[1]*b[i1] + a[2]*b[i2] + a[3]*b[i3] is maximized. Return the maximum score you can achieve.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_score(a: Vec<i32>, b: Vec<i32>) -> i64 {
    let n = b.len();
    // dp[j] = max score using a[0..j] with last picked index < current
    // dp[j][i] = max score when we've selected j elements from b[0..=i]
    // dp[0] = 0 (no elements picked yet)
    // Transition: dp[j+1][i] = max(dp[j+1][i-1], dp[j][i-1] + a[j]*b[i])
    
    const NEG_INF: i64 = i64::MIN / 2;
    let mut dp = vec![NEG_INF; 5];
    dp[0] = 0;
    
    for i in 0..n {
      // Process in reverse to avoid overwriting
      for j in (0..4).rev() {
        if dp[j] != NEG_INF {
          let val = dp[j] + a[j] as i64 * b[i] as i64;
          if val > dp[j + 1] {
            dp[j + 1] = val;
          }
        }
      }
    }
    dp[4]
  }
}