Skip to content

1458. Max Dot Product of Two Subsequences 👍

  • Time: $O(mn)$
  • Space: $O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
    const int m = nums1.size();
    const int n = nums2.size();
    // dp[i][j] := the maximum dot product of the two subsequences nums[0..i)
    // and nums2[0..j)
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MIN));

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        dp[i + 1][j + 1] = max({dp[i][j + 1], dp[i + 1][j],
                                max(0, dp[i][j]) + nums1[i] * nums2[j]});

    return dp[m][n];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
  public int maxDotProduct(int[] nums1, int[] nums2) {
    final int m = nums1.length;
    final int n = nums2.length;
    // dp[i][j] := the maximum dot product of the two subsequences nums[0..i)
    // and nums2[0..j)
    int[][] dp = new int[m + 1][n + 1];
    Arrays.stream(dp).forEach(A -> Arrays.fill(A, Integer.MIN_VALUE));

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        dp[i + 1][j + 1] = Math.max(Math.max(dp[i][j + 1], dp[i + 1][j]),
                                    Math.max(0, dp[i][j]) + nums1[i] * nums2[j]);

    return dp[m][n];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  def maxDotProduct(self, A: List[int], B: List[int]) -> int:
    m = len(A)
    n = len(B)
    # dp[i][j] := the maximum dot product of the two subsequences nums[0..i)
    # and nums2[0..j)
    dp = [[-math.inf] * (n + 1) for _ in range(m + 1)]

    for i in range(m):
      for j in range(n):
        dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j],
                               max(0, dp[i][j]) + A[i] * B[j])

    return dp[m][n]