leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1458.cpp (997B)

      1 class Solution {
      2     static int dp[501], pdp[501];
      3 
      4   public:
      5     int maxDotProduct(const vector<int> &nums1, const vector<int> &nums2) {
      6         int maxi1 = INT_MIN, maxi2 = INT_MIN;
      7         int mini1 = INT_MAX, mini2 = INT_MAX;
      8 
      9         for (const int n : nums1) {
     10             maxi1 = max(maxi1, n);
     11             mini1 = min(mini1, n);
     12         }
     13 
     14         for (const int n : nums2) {
     15             maxi2 = max(maxi2, n);
     16             mini2 = min(mini2, n);
     17         }
     18 
     19         if (maxi1 < 0 && mini2 > 0) return maxi1 * mini2;
     20         if (mini1 > 0 && maxi2 < 0) return mini1 * maxi2;
     21 
     22         memset(dp, 0x00, sizeof(dp));
     23         memset(pdp, 0x00, sizeof(pdp));
     24         for (int i = nums1.size() - 1; i >= 0; i--) {
     25             for (int j = nums2.size() - 1; j >= 0; j--) {
     26                 dp[j] = max({pdp[j], dp[j + 1], nums1[i] * nums2[j] + pdp[j + 1]});
     27             }
     28             memcpy(pdp, dp, sizeof(dp));
     29         }
     30 
     31         return dp[0];
     32     }
     33 };
     34 
     35 int Solution::dp[501], Solution::pdp[501];