07. Maximize dot product

The problem can be found at the following link: Question Link

My Approach

To solve this problem, we use dynamic programming. We initialize a 2D array dp of size (n+1) x (m+1) to store the maximum dot product for subarrays of a and b. - We initialize dp[0][j] to INT_MIN for handling cases where one of the arrays is empty.

• Then, we iterate over the arrays a and b, and for each pair of elements, we update dp[i][j] to be the maximum of either the dot product of the subarrays ending at index i and j or the dot product of the subarrays ending at index i-1 and j.

• Finally, we return dp[n][m] which represents the maximum dot product.

Time and Auxiliary Space Complexity

• Time Complexity : O(n * m), where n is the size of array a and m is the size of array b.

• Auxiliary Space Complexity : O(n * m), for the dp array.

Code (C++)

class Solution {
public:
    int maxDotProduct(int n, int m, int a[], int b[]) 
    { 
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        
        for (int j = 1; j <= m; ++j)
            dp[0][j] = INT_MIN;
        
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + a[i - 1] * b[j - 1]);
        
        return dp[n][m];
    } 
};

Contribution and Support

For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.

If you find this solution helpful, consider supporting us by giving a ⭐ star to the getlost01/gfg-potd repository.