Sponsored
Sponsored
This approach involves using dynamic programming to store results of subproblems and avoid redundant calculations.
We define a recursive helper function that considers each element from both arrays and decides whether to include it in the subsequence or not. The dynamic programming table stores the maximum dot product up to the current indices.
Time Complexity: O(m * n) where m and n are the sizes of the two arrays.
Space Complexity: O(m * n) for the dp table.
1#include <stdio.h>
2#include <limits.h>
3
4int max(int a, int b) {
5 return a > b ? a : b;
6}
7
8int maxDotProduct(int *nums1, int nums1Size, int *nums2, int nums2Size) {
9 int dp[501][501];
10 for (int i = 0; i <= nums1Size; i++) {
11 for (int j = 0; j <= nums2Size; j++) {
12 dp[i][j] = INT_MIN;
13 }
14 }
15 for (int i = 1; i <= nums1Size; i++) {
16 for (int j = 1; j <= nums2Size; j++) {
17 int prod = nums1[i-1] * nums2[j-1];
18 dp[i][j] = max(dp[i][j], prod + (i > 1 && j > 1 ? dp[i-1][j-1] : 0));
19 dp[i][j] = max(dp[i][j], dp[i-1][j]);
20 dp[i][j] = max(dp[i][j], dp[i][j-1]);
21 }
22 }
23 return dp[nums1Size][nums2Size];
24}
25
26int main() {
27 int nums1[] = {2, 1, -2, 5};
28 int nums2[] = {3, 0, -6};
29 int result = maxDotProduct(nums1, 4, nums2, 3);
30 printf("%d\n", result);
31 return 0;
32}This C implementation uses a 2D array dp where dp[i][j] stores the maximum dot product of subsequences up to the i-th index of nums1 and j-th index of nums2.
This approach involves using backtracking combined with memoization to efficiently enumerate possible subsequences, storing results for reused subsequence comparisons to enhance performance.
The memoization helps to prevent recalculating results for the same indices, transforming exponential time complexity to polynomial time complexity.
Time Complexity: O(m * n) where m and n are the lengths of nums1 and nums2. Although recursive, memoization reduces repeated work.
Space Complexity: O(m * n) for the memoization array.
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
vector<vector<int>> dp;
int dfs(const vector<int>& nums1, const vector<int>& nums2, int i, int j) {
if (i >= nums1.size() || j >= nums2.size()) return INT_MIN / 2;
if (dp[i][j] != INT_MIN) return dp[i][j];
int result = nums1[i] * nums2[j] + dfs(nums1, nums2, i + 1, j + 1);
result = max(result, dfs(nums1, nums2, i + 1, j));
result = max(result, dfs(nums1, nums2, i, j + 1));
result = max(result, nums1[i] * nums2[j]);
dp[i][j] = result;
return dp[i][j];
}
int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
dp = vector<vector<int>>(nums1.size(), vector<int>(nums2.size(), INT_MIN));
return dfs(nums1, nums2, 0, 0);
}
int main() {
vector<int> nums1 = {2, 1, -2, 5};
vector<int> nums2 = {3, 0, -6};
cout << maxDotProduct(nums1, nums2) << endl;
return 0;
}This C++ solution leverages recursive depth-first search combined with memoization. Again, a cache (dp array) is used to avoid redundant recursive calls by storing precomputed results.