leetcode

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];