Untitled
unknown
plain_text
2 years ago
989 B
5
Indexable
class Solution { public: int dp[501][501]; int f(int i, int j, vector<int>& A, vector<int>& B) { if (i >= A.size() || j >= B.size()) return 0; if (dp[i][j] != -1) return dp[i][j]; int op1 = A[i] * B[j] + f(i + 1, j + 1, A, B); int op2 = f(i + 1, j, A, B); int op3 = f(i, j + 1, A, B); return dp[i][j] = max({op1, op2, op3}); } int maxDotProduct(vector<int>& nums1, vector<int>& nums2) { int firstMax = *max_element(begin(nums1), end(nums1)); int secondMax = *max_element(begin(nums2), end(nums2)); int firstMin = *min_element(begin(nums1), end(nums1)); int secondMin = *min_element(begin(nums2), end(nums2)); if (firstMax < 0 && secondMin > 0) { return firstMax * secondMin; } if (firstMin > 0 && secondMax < 0) { return firstMin * secondMax; } memset(dp, -1, sizeof(dp)); return f(0, 0, nums1, nums2); } };
Editor is loading...
Leave a Comment