Max Dot Product of Two Subsequences LeetCode solution in C++

1
class Solution {
2
 public:
3
  const int NEG_INF = -10e8;
4
  int maxDotProduct(vector<int> &nums1, vector<int> &nums2) {
5
    int n = nums1.size();
6
    int m = nums2.size();
7

8
    // NOTE : we can't initialize with INT_MIN because adding any val with it
9
    // will give overflow that is why we prefer 10^7 or 10^8
10

11
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, NEG_INF));
12

13
    for (int i = 1; i <= n; i++) {
14
      for (int j = 1; j <= m; j++) {
15
        int temp_p = nums1[i - 1] * nums2[j - 1];
16

17
        // Although it is a variation of LCS but here we need to check for all
18
        // answers we already know in dp Why only temp_p ? -> suppose in
19
        // dp[i-1][j-1] is -10^7 + temp_p is 2 == gives nearly -10^7(which is
20
        // wrong ans) For Remaining comparisons we already know why !
21

22
        dp[i][j] = max({dp[i - 1][j - 1] + temp_p, temp_p, dp[i - 1][j], dp[i][j - 1]});
23
      }
24
    }
25

26
    return dp[n][m];
27
  }
28
};