leetcode

commit b2115756451ccfc1cbe355817eadb708be872f26
parent b39a7accfd5b553bda3c07da9be621450f1a3c38
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun,  8 Oct 2023 23:03:29 +0000

Daily Problem

Diffstat:
A
Problems/1458.cpp
 | 
35
+++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 36 insertions(+), 0 deletions(-)
diff --git a/Problems/1458.cpp b/Problems/1458.cpp
@@ -0,0 +1,35 @@
+class Solution {
+    static int dp[501], pdp[501];
+
+  public:
+    int maxDotProduct(const vector<int> &nums1, const vector<int> &nums2) {
+        int maxi1 = INT_MIN, maxi2 = INT_MIN;
+        int mini1 = INT_MAX, mini2 = INT_MAX;
+
+        for (const int n : nums1) {
+            maxi1 = max(maxi1, n);
+            mini1 = min(mini1, n);
+        }
+
+        for (const int n : nums2) {
+            maxi2 = max(maxi2, n);
+            mini2 = min(mini2, n);
+        }
+
+        if (maxi1 < 0 && mini2 > 0) return maxi1 * mini2;
+        if (mini1 > 0 && maxi2 < 0) return mini1 * maxi2;
+
+        memset(dp, 0x00, sizeof(dp));
+        memset(pdp, 0x00, sizeof(pdp));
+        for (int i = nums1.size() - 1; i >= 0; i--) {
+            for (int j = nums2.size() - 1; j >= 0; j--) {
+                dp[j] = max({pdp[j], dp[j + 1], nums1[i] * nums2[j] + pdp[j + 1]});
+            }
+            memcpy(pdp, dp, sizeof(dp));
+        }
+
+        return dp[0];
+    }
+};
+
+int Solution::dp[501], Solution::pdp[501];
diff --git a/README.md b/README.md
@@ -621,6 +621,7 @@ for solving problems.
 |  1451  |   Medium   | [Rearrange Words in a Sentence](Problems/1451.cpp)                                                 |
 |  1456  |   Medium   | [Maximum Number of Vowels in a Substring of Given Length](Problems/1456.cpp)                       |
 |  1457  |   Medium   | [Pseudo-Palindromic Paths in a Binary Tree](Problems/1457.cpp)                                     |
+|  1458  |    Hard    | [Max Dot Product of Two Subsequences](Problems/1458.cpp)                                           |
 |  1462  |   Medium   | [Course Schedule IV](Problems/1462.cpp)                                                            |
 |  1466  |   Medium   | [Reorder Routes to Make All Paths Lead to the City Zero](Problems/1466.cpp)                        |
 |  1470  |    Easy    | [Shuffle the Array](Problems/1470.cpp)                                                             |