leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1458.cpp (997B)

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