Given two integer arrays a[] and b[], the task is to find the maximum possible product of the same indexed elements of two equal length subsequences from the two given arrays.
Examples:
Input: a[] = {-3, 1, -12, 7}, b[] = {3, 2, -6, 7}
Output: 124
Explanation: The subsequence [1, -12, 7] from a[] and subsequence [3, -6, 7] from b[] gives the maximum scalar product, (1*3 + (-12)*(-6) + 7*7) = 124.Input: a[] = {-2, 6, -2, -5}, b[] = {-3, 4, -2, 8}
Output: 54
Explanation: The subsequence [-2, 6] from a[] and subsequence [-3, 8] from b[] gives the maximum scalar product, ((-2)*(-3) + 6*8) = 54.
Approach: The problem is similar to the Longest Common Subsequence problem of Dynamic Programming. A Recursive and Memoization based Top-Down method is explained below:
- Let us define a function F(X, Y), which returns the maximum scalar product between the arrays a[0-X] and b[0-Y].
- Following is the recursive definition:
F(X, Y) = max(a[X] * b[Y] + F(X – 1, Y – 1); Use the last elements from both arrays and check further
a[X] * b[Y]; Only use the last element as the maximum product
F(X – 1, Y); Ignore the last element from the first array
F(X, Y – 1)); Ignore the last element from the second element
- Use a 2-D array for memoization and to avoid recomputation of same sub-problems.
Below is the implementation of the above approach:
C++
// C++ implementation to maximize// product of same-indexed elements// of same size subsequences#include <bits/stdc++.h>using namespace std;#define INF 10000000// Utility function to find the maximumint maximum(int A, int B, int C, int D){ return max(max(A, B), max(C, D));}// Utility function to find// the maximum scalar product// from the equal length sub-sequences// taken from the two given arrayint maxProductUtil( int X, int Y, int* A, int* B, vector<vector<int> >& dp){ // Return a very small number // if index is invalid if (X < 0 or Y < 0) return -INF; // If the sub-problem is already // evaluated, then return it if (dp[X][Y] != -1) return dp[X][Y]; // Take the maximum of all // the recursive cases dp[X][Y] = maximum( A[X] * B[Y] + maxProductUtil( X - 1, Y - 1, A, B, dp), A[X] * B[Y], maxProductUtil( X - 1, Y, A, B, dp), maxProductUtil( X, Y - 1, A, B, dp)); return dp[X][Y];}// Function to find maximum scalar// product from same size sub-sequences// taken from the two given arrayint maxProduct(int A[], int N, int B[], int M){ // Initialize a 2-D array // for memoization vector<vector<int> > dp(N, vector<int>(M, -1)); return maxProductUtil( N - 1, M - 1, A, B, dp);}// Driver Codeint main(){ int a[] = { -2, 6, -2, -5 }; int b[] = { -3, 4, -2, 8 }; int n = sizeof(a) / sizeof(a[0]); int m = sizeof(b) / sizeof(b[0]); cout << maxProduct(a, n, b, m);} |
Java
// Java implementation to maximize// product of same-indexed elements// of same size subsequencesclass GFG{static final int INF = 10000000;// Utility function to find the maximumstatic int maximum(int A, int B, int C, int D){ return Math.max(Math.max(A, B), Math.max(C, D));}// Utility function to find the // maximum scalar product from // the equal length sub-sequences// taken from the two given arraystatic int maxProductUtil(int X, int Y, int []A, int[] B, int [][]dp){ // Return a very small number // if index is invalid if (X < 0 || Y < 0) return -INF; // If the sub-problem is already // evaluated, then return it if (dp[X][Y] != -1) return dp[X][Y]; // Take the maximum of all // the recursive cases dp[X][Y] = maximum(A[X] * B[Y] + maxProductUtil(X - 1, Y - 1, A, B, dp), A[X] * B[Y], maxProductUtil(X - 1, Y, A, B, dp), maxProductUtil(X, Y - 1, A, B, dp)); return dp[X][Y];}// Function to find maximum scalar// product from same size sub-sequences// taken from the two given arraystatic int maxProduct(int A[], int N, int B[], int M){ // Initialize a 2-D array // for memoization int [][]dp = new int[N][M]; for(int i = 0; i < N; i++) { for(int j = 0; j < M; j++) { dp[i][j] = -1; } } return maxProductUtil(N - 1, M - 1, A, B, dp);}// Driver Codepublic static void main(String[] args){ int a[] = { -2, 6, -2, -5 }; int b[] = { -3, 4, -2, 8 }; int n = a.length; int m = b.length; System.out.print(maxProduct(a, n, b, m));}}// This code is contributed by Amal Kumar Choubey |
Python3
# Python3 implementation to maximize # product of same-indexed elements # of same size subsequencesINF = 10000000# Utility function to find the maximum def maximum(A, B, C, D): return max(max(A, B), max(C, D))# Utility function to find # the maximum scalar product # from the equal length sub-sequences # taken from the two given array def maxProductUtil(X, Y, A, B, dp): # Return a very small number # if index is invalid if (X < 0 or Y < 0): return -INF # If the sub-problem is already # evaluated, then return it if (dp[X][Y] != -1): return dp[X][Y] # Take the maximum of all # the recursive cases dp[X][Y]= maximum(A[X] * B[Y] + maxProductUtil(X - 1, Y - 1, A, B, dp), A[X] * B[Y], maxProductUtil(X - 1, Y, A, B, dp), maxProductUtil(X, Y - 1, A, B, dp)) return dp[X][Y]# Function to find maximum scalar # product from same size sub-sequences # taken from the two given array def maxProduct(A, N, B, M): # Initialize a 2-D array # for memoization dp = [[-1 for i in range(m)] for i in range(n)] return maxProductUtil(N - 1, M - 1, A, B, dp)# Driver Codea = [ -2, 6, -2, -5 ]b = [ -3, 4, -2, 8 ]n = len(a)m = len(b)print(maxProduct(a, n, b, m))# This code is contributed by avanitrachhadiya2155 |
C#
// C# implementation to maximize// product of same-indexed elements// of same size subsequencesusing System;class GFG{static readonly int INF = 10000000;// Utility function to find the maximumstatic int maximum(int A, int B, int C, int D){ return Math.Max(Math.Max(A, B), Math.Max(C, D));}// Utility function to find the // maximum scalar product from // the equal length sub-sequences// taken from the two given arraystatic int maxProductUtil(int X, int Y, int []A, int[] B, int [,]dp){ // Return a very small number // if index is invalid if (X < 0 || Y < 0) return -INF; // If the sub-problem is already // evaluated, then return it if (dp[X, Y] != -1) return dp[X, Y]; // Take the maximum of all // the recursive cases dp[X, Y] = maximum(A[X] * B[Y] + maxProductUtil(X - 1, Y - 1, A, B, dp), A[X] * B[Y], maxProductUtil(X - 1, Y, A, B, dp), maxProductUtil(X, Y - 1, A, B, dp)); return dp[X, Y];}// Function to find maximum scalar// product from same size sub-sequences// taken from the two given arraystatic int maxProduct(int []A, int N, int []B, int M){ // Initialize a 2-D array // for memoization int [,]dp = new int[N, M]; for(int i = 0; i < N; i++) { for(int j = 0; j < M; j++) { dp[i, j] = -1; } } return maxProductUtil(N - 1, M - 1, A, B, dp);}// Driver Codepublic static void Main(String[] args){ int []a = { -2, 6, -2, -5 }; int []b = { -3, 4, -2, 8 }; int n = a.Length; int m = b.Length; Console.Write(maxProduct(a, n, b, m));}}// This code is contributed by amal kumar choubey |
Javascript
<script>// Javascript implementation to maximize// product of same-indexed elements// of same size subsequenceslet INF = 10000000; // Utility function to find the maximumfunction maximum(A, B, C, D){ return Math.max(Math.max(A, B), Math.max(C, D));} // Utility function to find the// maximum scalar product from// the equal length sub-sequences// taken from the two given arrayfunction maxProductUtil(X, Y, A, B, dp){ // Return a very small number // if index is invalid if (X < 0 || Y < 0) return -INF; // If the sub-problem is already // evaluated, then return it if (dp[X][Y] != -1) return dp[X][Y]; // Take the maximum of all // the recursive cases dp[X][Y] = maximum(A[X] * B[Y] + maxProductUtil(X - 1, Y - 1, A, B, dp), A[X] * B[Y], maxProductUtil(X - 1, Y, A, B, dp), maxProductUtil(X, Y - 1, A, B, dp)); return dp[X][Y];} // Function to find maximum scalar// product from same size sub-sequences// taken from the two given arrayfunction maxProduct(A, N, B, M){ // Initialize a 2-D array // for memoization let dp =new Array(N); for (var i = 0; i < dp.length; i++) { dp[i] = new Array(2); } for(let i = 0; i < N; i++) { for(let j = 0; j < M; j++) { dp[i][j] = -1; } } return maxProductUtil(N - 1, M - 1, A, B, dp);} // Driver Code let a = [ -2, 6, -2, -5 ]; let b = [ -3, 4, -2, 8 ]; let n = a.length; let m = b.length; document.write(maxProduct(a, n, b, m)); </script> |
Output
54
Efficient approach: Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Steps to solve this problem :
- Create a DP to store the solution of the subproblems and initialize it with 0.
- Initialize the DP with base cases dp[0][0] = A[0] * B[0].
- Now Iterate over subproblems to get the value of current problem form previous computation of subproblems stored in DP\
- Return the final solution stored in dp[N-1][M-1]
Implementation :
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;#define INF 10000000// Utility function to find the maximumint maximum(int A, int B, int C, int D){ return max(max(A, B), max(C, D));}// Utility function to find// the maximum scalar product// from the equal length sub-sequences// taken from the two given arrayint maxProduct(int A[], int N, int B[], int M){ // Initialize dp to store // computations of subproblems vector<vector<int>> dp(N, vector<int>(M, 0)); // Base case dp[0][0] = A[0] * B[0]; // Fill first row for (int j = 1; j < M; j++) { dp[0][j] = max(A[0] * B[j], dp[0][j-1]); } // Fill first column for (int i = 1; i < N; i++) { dp[i][0] = max(A[i] * B[0], dp[i-1][0]); } // Fill remaining cells for (int i = 1; i < N; i++) { for (int j = 1; j < M; j++) { dp[i][j] = maximum(A[i] * B[j] + dp[i-1][j-1], A[i] * B[j], dp[i-1][j], dp[i][j-1]); } } // return final answer return dp[N-1][M-1];}// Driver Codeint main(){ int a[] = { -2, 6, -2, -5 }; int b[] = { -3, 4, -2, 8 }; int n = sizeof(a) / sizeof(a[0]); int m = sizeof(b) / sizeof(b[0]); // function call cout << maxProduct(a, n, b, m);}// this code is contributed by bhardwajji |
Java
// Java program for above approachimport java.util.*;class Main { // Utility function to find the maximumstatic int maximum(int A, int B, int C, int D) {return Math.max(Math.max(A, B), Math.max(C, D));} // Utility function to find the maximum scalar product// from the equal length sub-sequences// taken from the two given arraysstatic int maxProduct(int[] A, int N, int[] B, int M) { // Initialize dp to store computations of subproblems int[][] dp = new int[N][M]; // Base case dp[0][0] = A[0] * B[0]; // Fill first row for (int j = 1; j < M; j++) { dp[0][j] = Math.max(A[0] * B[j], dp[0][j - 1]); } // Fill first column for (int i = 1; i < N; i++) { dp[i][0] = Math.max(A[i] * B[0], dp[i - 1][0]); } // Fill remaining cells for (int i = 1; i < N; i++) { for (int j = 1; j < M; j++) { dp[i][j] = maximum(A[i] * B[j] + dp[i - 1][j - 1], A[i] * B[j], dp[i - 1][j], dp[i][j - 1]); } } // return final answer return dp[N - 1][M - 1];}// Driver Codepublic static void main(String[] args) { int a[] = { -2, 6, -2, -5 }; int b[] = { -3, 4, -2, 8 }; int n = a.length; int m = b.length; // function call System.out.println(maxProduct(a, n, b, m));}} |
Python3
def maximum(A, B, C, D): return max(max(A, B), max(C, D))def maxProduct(A, N, B, M): # Initialize dp to store computations of subproblems dp = [[0] * M for _ in range(N)] # Base case dp[0][0] = A[0] * B[0] # Fill first row for j in range(1, M): dp[0][j] = max(A[0] * B[j], dp[0][j-1]) # Fill first column for i in range(1, N): dp[i][0] = max(A[i] * B[0], dp[i-1][0]) # Fill remaining cells for i in range(1, N): for j in range(1, M): dp[i][j] = maximum(A[i] * B[j] + dp[i-1][j-1], A[i] * B[j], dp[i-1][j], dp[i][j-1]) # Return final answer return dp[N-1][M-1]# Driver Codea = [-2, 6, -2, -5]b = [-3, 4, -2, 8]n = len(a)m = len(b)# Function callprint(maxProduct(a, n, b, m)) |
C#
using System;class MainClass { // Utility function to find the maximum static int Maximum(int A, int B, int C, int D) { return Math.Max(Math.Max(A, B), Math.Max(C, D)); } // Utility function to find the maximum scalar product // from the equal length sub-sequences // taken from the two given arrays static int MaxProduct(int[] A, int N, int[] B, int M) { // Initialize dp to store computations of // subproblems int[, ] dp = new int[N, M]; // Base case dp[0, 0] = A[0] * B[0]; // Fill first row for (int j = 1; j < M; j++) { dp[0, j] = Math.Max(A[0] * B[j], dp[0, j - 1]); } // Fill first column for (int i = 1; i < N; i++) { dp[i, 0] = Math.Max(A[i] * B[0], dp[i - 1, 0]); } // Fill remaining cells for (int i = 1; i < N; i++) { for (int j = 1; j < M; j++) { dp[i, j] = Maximum( A[i] * B[j] + dp[i - 1, j - 1], A[i] * B[j], dp[i - 1, j], dp[i, j - 1]); } } // return final answer return dp[N - 1, M - 1]; } // Driver Code public static void Main(string[] args) { int[] a = { -2, 6, -2, -5 }; int[] b = { -3, 4, -2, 8 }; int n = a.Length; int m = b.Length; // function call Console.WriteLine(MaxProduct(a, n, b, m)); }}// The code is contributed by Samim Hossain Mondal. |
Javascript
//Javascript code for this approach// Utility function to find the maximumfunction maximum(A, B, C, D) { return Math.max(Math.max(A, B), Math.max(C, D));}// Utility function to find// the maximum scalar product// from the equal length sub-sequences// taken from the two given arraysfunction maxProduct(A, N, B, M) { // Initialize dp to store computations of subproblems let dp = new Array(N).fill().map(() => new Array(M).fill(0)); // Base case dp[0][0] = A[0] * B[0]; // Fill first row for (let j = 1; j < M; j++) { dp[0][j] = Math.max(A[0] * B[j], dp[0][j-1]); } // Fill first column for (let i = 1; i < N; i++) { dp[i][0] = Math.max(A[i] * B[0], dp[i-1][0]); } // Fill remaining cells for (let i = 1; i < N; i++) { for (let j = 1; j < M; j++) { dp[i][j] = maximum(A[i] * B[j] + dp[i-1][j-1], A[i] * B[j], dp[i-1][j], dp[i][j-1]); } } // return final answer return dp[N-1][M-1];}// Driver Codelet a = [ -2, 6, -2, -5 ];let b = [ -3, 4, -2, 8 ];let n = a.length;let m = b.length;// function callconsole.log(maxProduct(a, n, b, m));// This code is contributed by Sundaram |
Output
54
Time complexity: O(N*M)
Auxiliary Space: O(N*M)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
