Welcome to Subscribe On Youtube

3290. Maximum Multiplication Score

Description

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, and i3 from the array b such that i0 < i1 < i2 < i3. Your score will be equal to the value a[0] * b[i0] + a[1] * b[i1] + a[2] * b[i2] + a[3] * b[i3].

Return the maximum score you can achieve.

 

Example 1:

Input: a = [3,2,5,6], b = [2,-6,4,-5,-3,2,-7]

Output: 26

Explanation:
We can choose the indices 0, 1, 2, and 5. The score will be 3 * 2 + 2 * (-6) + 5 * 4 + 6 * 2 = 26.

Example 2:

Input: a = [-1,4,5,-2], b = [-5,-1,-3,-2,-4]

Output: -1

Explanation:
We can choose the indices 0, 1, 3, and 4. The score will be (-1) * (-5) + 4 * (-1) + 5 * (-2) + (-2) * (-4) = -1.

 

Constraints:

• a.length == 4
• 4 <= b.length <= 105
• -105 <= a[i], b[i] <= 105

Solutions

Solution 1: Memoization

We design a function $\textit{dfs}(i, j)$, which represents the maximum score that can be obtained starting from the $i$-th element of array $a$ and the $j$-th element of array $b$. Then the answer is $\textit{dfs}(0, 0)$.

The function $\textit{dfs}(i, j)$ is calculated as follows:

• If $j \geq \text{len}(b)$, it means array $b$ has been completely traversed. At this point, if array $a$ has also been completely traversed, return $0$; otherwise, return negative infinity.
• If $i \geq \text{len}(a)$, it means array $a$ has been completely traversed. Return $0$.
• Otherwise, we can either skip the $j$-th element of array $b$ and move to the next element, i.e., $\textit{dfs}(i, j + 1)$; or we can choose the $j$-th element of array $b$, in which case the score is $a[i] \times b[j]$ plus $\textit{dfs}(i + 1, j + 1)$. We take the maximum of these two values as the return value of $\textit{dfs}(i, j)$.

We can use memoization to avoid redundant calculations.

The time complexity is $O(m \times n)$, and the space complexity is $O(m \times n)$. Here, $m$ and $n$ are the lengths of arrays $a$ and $b$, respectively.

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      private Long[][] f;
      private int[] a;
      private int[] b;
  
      public long maxScore(int[] a, int[] b) {
          f = new Long[a.length][b.length];
          this.a = a;
          this.b = b;
          return dfs(0, 0);
      }
  
      private long dfs(int i, int j) {
          if (j >= b.length) {
              return i >= a.length ? 0 : Long.MIN_VALUE / 2;
          }
          if (i >= a.length) {
              return 0;
          }
          if (f[i][j] != null) {
              return f[i][j];
          }
          return f[i][j] = Math.max(dfs(i, j + 1), 1L * a[i] * b[j] + dfs(i + 1, j + 1));
      }
  }
  
  

• class Solution {
  public:
      long long maxScore(vector<int>& a, vector<int>& b) {
          int m = a.size(), n = b.size();
          long long f[m][n];
          memset(f, -1, sizeof(f));
          auto dfs = [&](auto&& dfs, int i, int j) -> long long {
              if (j >= n) {
                  return i >= m ? 0 : LLONG_MIN / 2;
              }
              if (i >= m) {
                  return 0;
              }
              if (f[i][j] != -1) {
                  return f[i][j];
              }
              return f[i][j] = max(dfs(dfs, i, j + 1), 1LL * a[i] * b[j] + dfs(dfs, i + 1, j + 1));
          };
          return dfs(dfs, 0, 0);
      }
  };
  
  

• class Solution:
      def maxScore(self, a: List[int], b: List[int]) -> int:
          @cache
          def dfs(i: int, j: int) -> int:
              if j >= len(b):
                  return 0 if i >= len(a) else -inf
              if i >= len(a):
                  return 0
              return max(dfs(i, j + 1), a[i] * b[j] + dfs(i + 1, j + 1))
  
          return dfs(0, 0)
  
  

• func maxScore(a []int, b []int) int64 {
  	m, n := len(a), len(b)
  	f := make([][]int64, m)
  	for i := range f {
  		f[i] = make([]int64, n)
  		for j := range f[i] {
  			f[i][j] = -1
  		}
  	}
  	var dfs func(i, j int) int64
  	dfs = func(i, j int) int64 {
  		if j >= n {
  			if i >= m {
  				return 0
  			}
  			return math.MinInt64 / 2
  		}
  		if i >= m {
  			return 0
  		}
  		if f[i][j] != -1 {
  			return f[i][j]
  		}
  		f[i][j] = max(dfs(i, j+1), int64(a[i])*int64(b[j])+dfs(i+1, j+1))
  		return f[i][j]
  	}
  	return dfs(0, 0)
  }
  
  

• function maxScore(a: number[], b: number[]): number {
      const [m, n] = [a.length, b.length];
      const f: number[][] = Array.from({ length: m }, () => Array(n).fill(-1));
      const dfs = (i: number, j: number): number => {
          if (j >= n) {
              return i >= m ? 0 : -Infinity;
          }
          if (i >= m) {
              return 0;
          }
          if (f[i][j] !== -1) {
              return f[i][j];
          }
          return (f[i][j] = Math.max(dfs(i, j + 1), a[i] * b[j] + dfs(i + 1, j + 1)));
      };
      return dfs(0, 0);
  }
  
  

All Problems

All Solutions