• Time:O(mn)
• Space:O(mn)

## C++

``````class Solution {
public:
int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
const int m = nums1.size();
const int n = nums2.size();
// dp[i][j] := max dot product of two subseqs 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];
}
};
``````

## JAVA

``````class Solution {
public int maxDotProduct(int[] nums1, int[] nums2) {
final int m = nums1.length;
final int n = nums2.length;
// dp[i][j] := max dot product of two subseqs nums[0..i) and nums2[0..j)
int[][] dp = new int[m + 1][n + 1];
Arrays.stream(dp).forEach(row -> Arrays.fill(row, 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];
}
}
``````

## Python

``````class Solution:
def maxDotProduct(self, A: List[int], B: List[int]) -> int:
m = len(A)
n = len(B)
# dp[i][j] := max dot product of two subseqs 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]
``````