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.
1using System;
2
3public class Solution {
4 public int MaxDotProduct(int[] nums1, int[] nums2) {
5 int m = nums1.Length, n = nums2.Length;
6 int[,] dp = new int[m + 1, n + 1];
7 for (int i = 0; i <= m; ++i)
8 for (int j = 0; j <= n; ++j)
9 dp[i, j] = int.MinValue;
10 for (int i = 1; i <= m; i++) {
11 for (int j = 1; j <= n; j++) {
12 int prod = nums1[i - 1] * nums2[j - 1];
13 dp[i, j] = Math.Max(dp[i, j], prod);
14 if (i > 1 && j > 1) dp[i, j] = Math.Max(dp[i, j], prod + dp[i - 1, j - 1]);
15 dp[i, j] = Math.Max(dp[i, j], dp[i - 1, j]);
16 dp[i, j] = Math.Max(dp[i, j], dp[i, j - 1]);
17 }
18 }
19 return dp[m, n];
20 }
21
22 public static void Main() {
23 int[] nums1 = {2, 1, -2, 5};
24 int[] nums2 = {3, 0, -6};
25 Solution sol = new Solution();
26 Console.WriteLine(sol.MaxDotProduct(nums1, nums2));
27 }
28}
This C# program employs a two-dimensional array for storing temporary results as it calculates the maximum dot product subsequences. It processes each possible element pairwise, updating the dp array accordingly.
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.
public class Solution {
private int[,] dp;
private int Dfs(int[] nums1, int[] nums2, int i, int j) {
if (i >= nums1.Length || j >= nums2.Length) return int.MinValue / 2;
if (dp[i, j] != int.MinValue) return dp[i, j];
int prod = nums1[i] * nums2[j];
int result = prod + Dfs(nums1, nums2, i + 1, j + 1);
result = Math.Max(result, Dfs(nums1, nums2, i + 1, j));
result = Math.Max(result, Dfs(nums1, nums2, i, j + 1));
result = Math.Max(result, prod);
dp[i, j] = result;
return dp[i, j];
}
public int MaxDotProduct(int[] nums1, int[] nums2) {
dp = new int[nums1.Length, nums2.Length];
for (int i = 0; i < nums1.Length; i++)
for (int j = 0; j < nums2.Length; j++)
dp[i, j] = int.MinValue;
return Dfs(nums1, nums2, 0, 0);
}
public static void Main() {
int[] nums1 = {2, 1, -2, 5};
int[] nums2 = {3, 0, -6};
Solution sol = new Solution();
Console.WriteLine(sol.MaxDotProduct(nums1, nums2));
}
}
In this C# approach, recursive exploration is performed starting from the start of both arrays, caching the results of potential subsequence products in a 2D dp
array.