Untitled

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);
    }
};