Max Dot Product of Two Subsequences

class Solution {
public:
    int maxDotProduct(vector<int>& arr1, vector<int>& arr2) {
        int max1 = INT_MIN, max2 = INT_MIN;
        int min1 = INT_MAX, min2 = INT_MAX;
        
        for (int element : arr1) {
            max1 = max(max1, element);
            min1 = min(min1, element);
        }
        
        for (int element : arr2) {
            max2 = max(max2, element);
            min2 = min(min2, element);
        }
        
        if (max1 < 0 && min2 > 0) {
            return max1 * min2;
        }
        
        if (min1 > 0 && max2 < 0) {
            return min1 * max2;
        } 

        int length = arr2.size() + 1;
        vector<int> current(length, 0);
        vector<int> prev(length, 0);
        
        for (int i = arr1.size() - 1; i >= 0; i--) {
            current = vector<int>(length, 0);
            for (int j = arr2.size() - 1; j >= 0; j--) {
                int productSum = arr1[i] * arr2[j] + prev[j + 1];
                current[j] = max(productSum, max(prev[j], current[j + 1]));
            }
            
            prev = current;
        }
        
        return current[0];
    }
};

To solve the problem of finding the maximum dot product of two subsequences using C++, the provided solution performs the following:

• Initialize Variables: Establish variables for tracking the maximum and minimum values of the two arrays. These help in determining edge cases where all elements in one array are negative and all in the other are positive or vice versa.

• Check for Edge Cases:

  • If the maximum value in the first array is negative and the minimum value in the second array is positive, the result is the product of these two values.
  • If the minimum value in the first array is positive and the maximum value in the second array is negative, then the result is the product of these values.

• Dynamic Programming Approach:

  • Use two vectors, current and prev, initialized to the size of the second array plus one. These vectors store the results of subproblems, enabling an efficient build-up to the final solution.
  • Iterate backwards through both arrays, calculating potential dot products for every subsequence pair. Update the current vector based on the maximum of:
    • The dot product of the current elements from both arrays plus the result of the best subsequence excluding the current elements.
    • The best result excluding the current element from the second array.
    • The result from processing previous elements.
  • After processing each element from the first array, copy the current vector to prev to prepare for the next iteration.

• Return the Result: The first element of the current vector after processing all elements contains the maximum dot product of two subsequences.

Through this approach, you efficiently address both the direct computation and the rule-based scenarios using conditional logic and dynamic programming.

class Solution {    
    public int maximumDotProduct(int[] array1, int[] array2) {
        int topMax = Integer.MIN_VALUE;
        int nextMax = Integer.MIN_VALUE;
        int topMin = Integer.MAX_VALUE;
        int nextMin = Integer.MAX_VALUE;
        
        for (int val: array1) {
            topMax = Math.max(topMax, val);
            topMin = Math.min(topMin, val);
        }
        
        for (int val: array2) {
            nextMax = Math.max(nextMax, val);
            nextMin = Math.min(nextMin, val);
        }
        
        if (topMax < 0 && nextMin > 0) {
            return topMax * nextMin;
        }
        
        if (topMin > 0 && nextMax < 0) {
            return topMin * nextMax;
        }

        int n = array2.length + 1;
        int[] currentDp = new int[n];
        int[] previousDp = new int[n];
        
        for (int i = array1.length - 1; i >= 0; i--) {
            currentDp = new int[n];
            for (int j = array2.length - 1; j >= 0; j--) {
                int choose = array1[i] * array2[j] + previousDp[j + 1];
                currentDp[j] = Math.max(choose, Math.max(previousDp[j], currentDp[j + 1]));
            }
            
            previousDp = currentDp;
        }
        
        return currentDp[0];
    }
}

The provided Java solution calculates the maximum dot product of two subsequences from given integer arrays. The maximumDotProduct function efficiently finds this value through dynamic programming and straightforward logic checks. The following summarizes the method and logic:

• First, identify the maximum (topMax) and minimum (topMin) values in array1, and the maximum (nextMax) and minimum (nextMin) values in array2 using for-loops.
• Handle specific cases where the maximum or minimum values across the arrays are only positive or negative. These cases optimize scenarios where multiplying the smallest and largest negative and positive integers respectively might render the maximum dot product:
  • If topMax is negative and nextMin is positive, return the multiplication of topMax * nextMin.
  • If topMin is positive and nextMax is negative, return the multiplication of topMin * nextMax.
• Use a dynamic programming approach to handle the general case:
  • Initialize two arrays, currentDp and previousDp, to track states. currentDp corresponds to potential max dot products at the current iteration, and previousDp to the previous iteration.
  • Traverse the arrays array1 and array2 in reverse to consider all possible subsequences. Calculate potential dot products by deciding whether to include or exclude current elements from array1 and array2.
  • The final result, representing the maximum dot product of two subsequences, is stored in currentDp[0].

By following this procedure, the program ensures optimal and efficient computation of the maximum dot product between two subsequences of the provided integer arrays. This method leverages both simple condition checks and a more complex dynamic programming technique, making it adaptable to various input conditions.

class Solution:
    def maximumDotProduct(self, list1: List[int], list2: List[int]) -> int:
        if max(list1) < 0 and min(list2) > 0:
            return max(list1) * min(list2)
        
        if min(list1) > 0 and max(list2) < 0:
            return min(list1) * max(list2)
        
        len_list2 = len(list2) + 1
        previous = [0] * len_list2
        current = [0] * len_list2
        
        for i in range(len(list1) - 1, -1, -1):
            current = [0] * len_list2
            for j in range(len(list2) - 1, -1, -1):
                choice1 = list1[i] * list2[j] + previous[j + 1]
                current[j] = max(choice1, previous[j], current[j + 1])
            
            previous = current
        
        return current[0]

The given solution calculates the maximum dot product between any subsequence of two lists of integers, list1 and list2, using dynamic programming in Python. Here's a breakdown of how the function implemented in the Solution class works to achieve this:

• First, the function checks if all elements in list1 are negative and all elements in list2 are positive or vice versa. If this condition is met, then the maximum dot product is simply the product of the maximum value in the smaller list with the minimum value in the larger list.
• The solution initializes two lists, previous and current, both filled with zeros and sized based on the length of list2 plus one. These lists are used to store intermediate results and update values for each iteration.
• A nested loop iterates backward through each element in list1 and list2. For each pair of elements, the function computes the possible dot product values:
  • choice1 handles the case where both elements from list1 and list2 are included in the subsequences being considered.
  • The values in the current array are updated based on the maximum of choice1, keeping the previous value in list1 (previous[j]), or excluding the current element in list2 (current[j + 1]).
• After iterating through all elements, previous is updated with the values of current to carry forward the computation to the next element of list1.
• Once all iterations are complete, current[0] contains the maximum dot product of two subsequences from list1 and list2.

This approach efficiently finds the maximum dot product by utilizing dynamic programming to avoid redundant calculations, thus optimizing performance for larger lists.