Maximise sum of product of pairs by choosing subsequence of same length from given Arrays
Given two integer arrays A[] and B[] of different length N and M respectively, the task is to choose any subsequence of same length from each array such that sum of product of pairs at corresponding indices in the subsequence is maximised.
Example:
Input: A = {4, -1, -3, 3}, B = {-4, 0, 5}
Output: 27
Explanation: Choosing subsequence {-3, 3} from A and subsequence {-4, 5} from B will give the maximum sum,
i.e. = (-3)*(-4) + 3*5 = 12 + 15 = 27Input: A = {-5, -1}, B = {2, 1, 4}
Output: -1
Explanation: The maximum sum of products possible is (-1)*1 = -1
Naive Approach: When carefully observed, actually we need to find optimal subsequences of equal length (>=1) from each array, such that summation of the products of elements from these subsequences is maximum.
So by using hit and trial method, we can use a recursive approach with to “choose or not choose” each element from both arrays, and find the optimal subsequence from all possible subsequences.
Below is the implementation of the recursive approach.
C++
// C++ program to Find the maximum summation of // products of pair of elements from two arrays // with negative numbers. #include <bits/stdc++.h> using namespace std; int MaxSOP(vector< int >& a, vector< int >& b, int n, int m, int taken) { // To ensure we take // at least one element if ((n == 0 || m == 0) && taken == 0) return -9999999; // Else if we cant take // any more elements that // is come to an end // of any array return 0 else if ((n == 0 || m == 0) && taken != 0) return 0; // Take the product & increment taken // skip element from a[] // skip element from b[] return max( { a[n - 1] * b[m - 1] + MaxSOP(a, b, n - 1, m - 1, taken + 1), MaxSOP(a, b, n - 1, m, taken), MaxSOP(a, b, n, m - 1, taken) }); } // Driver code int main() { vector< int > a = { 4, -1, -3, 3 }; vector< int > b = { -4, 0, 5 }; int ans = MaxSOP(a, b, a.size(), b.size(), 0); cout << ans << endl; return 0; } |
Java
// JAVA program to Find the maximum summation of // products of pair of elements from two arrays // with negative numbers. import java.util.*; class GFG { public static int MaxSOP( int a[], int b[], int n, int m, int taken) { // To ensure we take // at least one element if ((n == 0 || m == 0 ) && taken == 0 ) return - 9999999 ; // Else if we cant take // any more elements that // is come to an end // of any array return 0 else if ((n == 0 || m == 0 ) && taken != 0 ) return 0 ; // Take the product & increment taken // skip element from a[] // skip element from b[] return Math.max( Math.max( a[n - 1 ] * b[m - 1 ] + MaxSOP(a, b, n - 1 , m - 1 , taken + 1 ), MaxSOP(a, b, n - 1 , m, taken)), MaxSOP(a, b, n, m - 1 , taken)); } // Driver code public static void main(String[] args) { int a[] = { 4 , - 1 , - 3 , 3 }; int b[] = { - 4 , 0 , 5 }; int ans = MaxSOP(a, b, a.length, b.length, 0 ); System.out.print(ans); } } // This code is contributed by rakeshsahni |
Python3
# Python3 program to Find the maximum summation of # products of pair of elements from two arrays # with negative numbers. def MaxSOP(a, b, n, m, taken): # To ensure we take # at least one element if ((n = = 0 or m = = 0 ) and taken = = 0 ): return - 9999999 # Else if we cant take # any more elements that # is come to an end # of any array return 0 elif ((n = = 0 or m = = 0 ) and taken ! = 0 ): return 0 # Take the product & increment taken # skip element from a[] # skip element from b[] return max (a[n - 1 ] * b[m - 1 ] + MaxSOP(a, b, n - 1 ,m - 1 , taken + 1 ),MaxSOP(a, b, n - 1 , m, taken),MaxSOP(a, b, n, m - 1 , taken)) # Driver code a = [ 4 , - 1 , - 3 , 3 ] b = [ - 4 , 0 , 5 ] ans = MaxSOP(a, b, len (a), len (b), 0 ) print (ans) # This code is contributed by shinjanpatra |
C#
// C# program to Find the maximum summation of // products of pair of elements from two arrays // with negative numbers. using System; class GFG { static int MaxSOP( int [] a, int [] b, int n, int m, int taken) { // To ensure we take // at least one element if ((n == 0 || m == 0) && taken == 0) return -9999999; // Else if we cant take // any more elements that // is come to an end // of any array return 0 else if ((n == 0 || m == 0) && taken != 0) return 0; // Take the product & increment taken // skip element from a[] // skip element from b[] return Math.Max( a[n - 1] * b[m - 1] + MaxSOP(a, b, n - 1, m - 1, taken + 1), Math.Max(MaxSOP(a, b, n - 1, m, taken), MaxSOP(a, b, n, m - 1, taken))); } // Driver code public static void Main() { int [] a = { 4, -1, -3, 3 }; int [] b = { -4, 0, 5 }; int ans = MaxSOP(a, b, a.Length, b.Length, 0); Console.Write(ans); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript program to Find the maximum summation of // products of pair of elements from two arrays // with negative numbers. function MaxSOP(a, b, n, m, taken) { // To ensure we take // at least one element if ((n == 0 || m == 0) && taken == 0) return -9999999; // Else if we cant take // any more elements that // is come to an end // of any array return 0 else if ((n == 0 || m == 0) && taken != 0) return 0; // Take the product & increment taken // skip element from a[] // skip element from b[] return Math.max(a[n - 1] * b[m - 1] + MaxSOP(a, b, n - 1, m - 1, taken + 1), MaxSOP(a, b, n - 1, m, taken), MaxSOP(a, b, n, m - 1, taken)); } // Driver code let a = [ 4, -1, -3, 3 ] let b = [ -4, 0, 5 ] let ans = MaxSOP(a, b, a.length, b.length, 0) document.write(ans, "</br>" ) // This code is contributed by shinjanpatra </script> |
27
Time Complexity: O(3N), as we are calling the function 3 times.
Auxiliary Space: O(1) (Recursion stack is not taken into consideration)
Efficient Approach: The exponential time complexity of Naive approach, due to recursion, can be optimized with Dynamic programming.
Memoize the recursive code and store the results in a matrix, so that when an overlapping sub-problem is found, directly return the result of it from the matrix. This will reduce the depth of the recursion and reduce the time complexity.
As we have three changing parameters, we will require 3D DP-array to store the values
Below is the implementation of the above approach:
C++
// C++ program to Find the maximum summation of // products of pair of elements from two arrays // with negative numbers. #include <bits/stdc++.h> using namespace std; // 3D array for memoization int t[101][101][101]; int MaxSOP(vector< int >& a, vector< int >& b, int n, int m, int taken) { // If taken = 0, therefore empty subsequence // So return highly negative value if ((n == 0 || m == 0) && taken == 0) return -9999999; // Else if we cant take any more elements // that is come to an end // of any array return 0 else if ((n == 0 || m == 0) && taken != 0) return 0; if (t[n][m][taken] != -1) // If value is previously calculated // return it directly return t[n][m][taken]; return t[n][m][taken] = max({ a[n - 1] * b[m - 1] + MaxSOP(a, b, n - 1, m - 1, taken + 1), MaxSOP(a, b, n - 1, m, taken), MaxSOP(a, b, n, m - 1, taken) }); } // Driver code int main() { vector< int > a = { 4, -1, -3, 3 }; vector< int > b = { -4, 0, 5 }; memset (t, -1, sizeof (t)); int ans = MaxSOP(a, b, a.size(), b.size(), 0); cout << ans << endl; return 0; } |
Java
// Java program to Find the maximum summation of // products of pair of elements from two arrays // with negative numbers. import java.util.*; public class GFG { // 3D array for memoization static int t[][][] = new int [ 101 ][ 101 ][ 101 ]; static int MaxSOP( int [] a, int [] b, int n, int m, int taken) { // If taken = 0, therefore empty subsequence // So return highly negative value if ((n == 0 || m == 0 ) && taken == 0 ) return - 9999999 ; // Else if we cant take any more elements // that is come to an end // of any array return 0 else if ((n == 0 || m == 0 ) && taken != 0 ) return 0 ; if (t[n][m][taken] != - 1 ) // If value is previously calculated // return it directly return t[n][m][taken]; return t[n][m][taken] = Math.max( a[n - 1 ] * b[m - 1 ] + MaxSOP(a, b, n - 1 , m - 1 , taken + 1 ), Math.max(MaxSOP(a, b, n - 1 , m, taken), MaxSOP(a, b, n, m - 1 , taken))); } // Driver code public static void main(String args[]) { int [] a = { 4 , - 1 , - 3 , 3 }; int [] b = { - 4 , 0 , 5 }; for ( int i = 0 ; i < 101 ; i++) { for ( int j = 0 ; j < 101 ; j++) { for ( int k = 0 ; k < 101 ; k++) { t[i][j][k] = - 1 ; } } } int ans = MaxSOP(a, b, a.length, b.length, 0 ); System.out.println(ans); } } // This code is contributed by Samim Hossain Mondal. |
Python3
# Python program to Find the maximum summation of # products of pair of elements from two arrays # with negative numbers. # 3D array for memoization t = [[ [ - 1 for col in range ( 101 )] for col in range ( 101 )] for row in range ( 101 )] def MaxSOP(a, b, n, m, taken): global t # If taken = 0, therefore empty subsequence # So return highly negative value if ((n = = 0 or m = = 0 ) and taken = = 0 ): return - 9999999 # Else if we cant take any more elements # that is come to an end # of any array return 0 elif ((n = = 0 or m = = 0 ) and taken ! = 0 ): return 0 if (t[n][m][taken] ! = - 1 ): # If value is previously calculated # return it directly return t[n][m][taken] t[n][m][taken] = max ( max (a[n - 1 ] * b[m - 1 ] + MaxSOP(a, b, n - 1 ,m - 1 ,taken + 1 ),MaxSOP(a, b, n - 1 , m, taken)),MaxSOP(a, b, n, m - 1 , taken)) return t[n][m][taken] # Driver code a = [ 4 , - 1 , - 3 , 3 ] b = [ - 4 , 0 , 5 ] ans = MaxSOP(a, b, len (a), len (b), 0 ) print (ans) # This code is contributed by shinjanpatra |
C#
// C# program to Find the maximum summation of // products of pair of elements from two arrays // with negative numbers. using System; class GFG { // 3D array for memoization static int [, , ] t = new int [101, 101, 101]; static int MaxSOP( int [] a, int [] b, int n, int m, int taken) { // If taken = 0, therefore empty subsequence // So return highly negative value if ((n == 0 || m == 0) && taken == 0) return -9999999; // Else if we cant take any more elements // that is come to an end // of any array return 0 else if ((n == 0 || m == 0) && taken != 0) return 0; if (t[n, m, taken] != -1) // If value is previously calculated // return it directly return t[n, m, taken]; return t[n, m, taken] = Math.Max( a[n - 1] * b[m - 1] + MaxSOP(a, b, n - 1, m - 1, taken + 1), Math.Max(MaxSOP(a, b, n - 1, m, taken), MaxSOP(a, b, n, m - 1, taken))); } // Driver code public static void Main() { int [] a = { 4, -1, -3, 3 }; int [] b = { -4, 0, 5 }; for ( int i = 0; i < 101; i++) { for ( int j = 0; j < 101; j++) { for ( int k = 0; k < 101; k++) { t[i, j, k] = -1; } } } int ans = MaxSOP(a, b, a.Length, b.Length, 0); Console.WriteLine(ans); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript program to Find the maximum summation of // products of pair of elements from two arrays // with negative numbers. // 3D array for memoization let t = new Array(101); for (let i = 0; i < 101; i++){ t[i] = new Array(101); for (let j = 0; j < 101; j++){ t[i][j] = new Array(101).fill(-1); } } function MaxSOP(a, b, n, m, taken) { // If taken = 0, therefore empty subsequence // So return highly negative value if ((n == 0 || m == 0) && taken == 0) return -9999999; // Else if we cant take any more elements // that is come to an end // of any array return 0 else if ((n == 0 || m == 0) && taken != 0) return 0; if (t[n][m][taken] != -1) // If value is previously calculated // return it directly return t[n][m][taken]; return t[n][m][taken] = Math.max(Math.max(a[n - 1] * b[m - 1]+ MaxSOP(a, b, n - 1, m - 1,taken + 1),MaxSOP(a, b, n - 1, m, taken)),MaxSOP(a, b, n, m - 1, taken)); } // Driver code let a = [ 4, -1, -3, 3 ];a let b = [ -4, 0, 5 ]; let ans = MaxSOP(a, b, a.length, b.length, 0); document.write(ans); // This code is contributed by shinjanpatra </script> |
27
Time Complexity: O(N3).
Auxiliary Space: O(N3), for using the extra 3D array.
More Efficient Approach: This above approach can be further optimized by reducing the state taken using the following observation:
In the above dynamic programming approach, we are concerned with only two states of taken: either 0 or not 0.
So instead of keeping multiple states of taken, it can be bound to two states 0 and 1.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Dp array int t[101][101][2]; // Function to count the maximum possible sum int MaxSOP(vector< int >& a, vector< int >& b, int n, int m, int taken) { // If taken==0, therefore empty subsequence // so return highly negative value if ((n == 0 || m == 0) && taken == 0) return -9999999; // Else if we cant take any more elements // that is come to an end of any array return 0 else if ((n == 0 || m == 0) && taken != 0) return 0; // If the value is pre-calculated // simply return it if (t[n][m][taken == 0 ? 0 : 1] != -1) return t[n][m][taken == 0 ? 0 : 1]; // Return and store the calculated value return t[n][m][taken == 0 ? 0 : 1] = max({ a[n - 1] * b[m - 1] + MaxSOP(a, b, n - 1, m - 1, taken + 1), MaxSOP(a, b, n - 1, m, taken), MaxSOP(a, b, n, m - 1, taken) }); } // Driver code int main() { vector< int > a = { 4, -1, -3, 3 }; vector< int > b = { -4, 0, 5 }; memset (t, -1, sizeof (t)); int ans = MaxSOP(a, b, a.size(), b.size(), 0); cout << ans << endl; return 0; } |
Java
// Java program to Find the maximum summation of // products of pair of elements from two arrays // with negative numbers. import java.util.*; class GFG { // DP array static int t[][][] = new int [ 101 ][ 101 ][ 101 ]; static int MaxSOP( int [] a, int [] b, int n, int m, int taken) { // If taken = 0, therefore empty subsequence // So return highly negative value if ((n == 0 || m == 0 ) && taken == 0 ) return - 9999999 ; // Else if we cant take any more elements // that is come to an end // of any array return 0 else if ((n == 0 || m == 0 ) && taken != 0 ) return 0 ; // If value is previously calculated // return it directly if (t[n][m][taken == 0 ? 0 : 1 ] != - 1 ) return t[n][m][taken == 0 ? 0 : 1 ]; return t[n][m][taken == 0 ? 0 : 1 ] = Math.max( a[n - 1 ] * b[m - 1 ] + MaxSOP(a, b, n - 1 , m - 1 , taken + 1 ), Math.max(MaxSOP(a, b, n - 1 , m, taken), MaxSOP(a, b, n, m - 1 , taken))); } // Driver code public static void main(String args[]) { int [] a = { 4 , - 1 , - 3 , 3 }; int [] b = { - 4 , 0 , 5 }; for ( int i = 0 ; i < 101 ; i++) { for ( int j = 0 ; j < 101 ; j++) { for ( int k = 0 ; k < 101 ; k++) { t[i][j][k] = - 1 ; } } } int ans = MaxSOP(a, b, a.length, b.length, 0 ); System.out.println(ans); } } // This code is contributed by Karandeep1234 |
Python3
# Python 3 program for the above approach import math # DP array t = [[[ 0 ] * 101 ] * 101 ] * 101 def MaxSOP(a, b, n, m, taken): # If taken = 0, therefore empty subsequence # So return highly negative value if ((n = = 0 or m = = 0 ) and taken = = 0 ): return - 9999999 # Else if we cant take any more elements # that is come to an end # of any array return 0 elif ((n = = 0 or m = = 0 ) and taken ! = 0 ) : return 0 # If value is previously calculated # return it directly if (t[n][m][ 0 if taken = = 0 else 1 ] ! = - 1 ): return t[n][m][ 0 if taken = = 0 else 1 ] return max (a[n - 1 ] * b[m - 1 ] + MaxSOP(a, b, n - 1 , m - 1 , taken + 1 ), max (MaxSOP(a, b, n - 1 , m, taken), MaxSOP(a, b, n, m - 1 , taken))) # Driver code if __name__ = = "__main__" : a = [ 4 , - 1 , - 3 , 3 ] b = [ - 4 , 0 , 5 ] for i in range ( 101 ) : for j in range ( 101 ) : for k in range ( 101 ) : t[i][j][k] = - 1 ans = MaxSOP(a, b, len (a), len (b), 0 ) print (ans) # This code is contributed by code_hunt. |
C#
// C# code to implement the approach using System; using System.Collections.Generic; class GFG { // Dp array static int [, , ] t = new int [101, 101, 2]; // Function to count the maximum possible sum static int MaxSOP(List< int > a, List< int > b, int n, int m, int taken) { // If taken==0, therefore empty subsequence // so return highly negative value if ((n == 0 || m == 0) && taken == 0) return -9999999; // Else if we cant take any more elements // that is come to an end of any array return 0 else if ((n == 0 || m == 0) && taken != 0) return 0; // If the value is pre-calculated // simply return it if (t[n, m, taken == 0 ? 0 : 1] != -1) return t[n, m, taken == 0 ? 0 : 1]; // Return and store the calculated value return t[n, m, taken == 0 ? 0 : 1] = Math.Max( Math.Max(a[n - 1] * b[m - 1] + MaxSOP(a, b, n - 1, m - 1, taken + 1), MaxSOP(a, b, n - 1, m, taken)), MaxSOP(a, b, n, m - 1, taken)); } // Driver code public static void Main() { List< int > a = new List< int >() { 4, -1, -3, 3 }; List< int > b = new List< int >() { -4, 0, 5 }; for ( int i = 0; i < 101; i++) for ( int j = 0; j < 101; j++) for ( int k = 0; k < 2; k++) t[i, j, k] = -1; int ans = MaxSOP(a, b, a.Count, b.Count, 0); Console.Write(ans); } } // This code is contributed by ukasp. |
Javascript
<script> // JavaScript program for the above approach // DP array let t = new Array(101); for (let i = 0; i < 101; i++) { t[i] = new Array(101); for (let j = 0; j < 101; j++) { t[i][j] = new Array(2).fill(0); } } function MaxSOP(a, b, n, m, taken){ // If taken = 0, therefore empty subsequence // So return highly negative value if ((n == 0 || m == 0) && taken == 0) return -9999999 // Else if we cant take any more elements // that is come to an end // of any array return 0 else if ((n == 0 || m == 0) && taken != 0) return 0 // If value is previously calculated // return it directly if (t[n][m][taken == 0 ? 0 : 1] != -1) return t[n][m][taken == 0 ? 0 : 1] return Math.max(a[n - 1] * b[m - 1] + MaxSOP(a, b, n - 1, m - 1, taken + 1), Math.max(MaxSOP(a, b, n - 1, m, taken), MaxSOP(a, b, n, m - 1, taken))) } // Driver code let a = [ 4, -1, -3, 3 ] let b = [ -4, 0, 5 ] for (let i = 0; i < 101; i++) { for (let j = 0; j < 101; j++) { for (let k = 0; k < 101; k++) { t[i][j][k] = -1 } } } let ans = MaxSOP(a, b, a.length, b.length, 0) document.write(ans) // This code is contributed by shinjanpatra </script> |
27
Time Complexity: O(N*M)
Auxiliary Space: O(N*M)
Bottom Up Approach:
Above approach can be space optimized by using iterative method instead of using recursive method which is taking extra stack space.
Below is the implementation of the same approach in Bottom-Up Manner.
C++
// C++ implementation of the bottom approach #include <bits/stdc++.h> using namespace std; int MaxSOP(vector< int >& a, vector< int >& b, int n, int m) { // Create a 3D DP table vector<vector<vector< int >>> dp(n + 1, vector<vector< int >>(m + 1, vector< int >(2, 0))); // Initialize the table with appropriate values for ( int i = 0; i <= n; i++) { for ( int j = 0; j <= m; j++) { dp[i][j][0] = -9999999; // Initialize as a large negative value dp[i][j][1] = 0; } } // Bottom-up approach to fill the DP table for ( int i = 1; i <= n; i++) { for ( int j = 1; j <= m; j++) { dp[i][j][0] = max(a[i - 1] * b[j - 1] + dp[i - 1][j - 1][1], max(dp[i - 1][j][0], dp[i][j - 1][0])); dp[i][j][1] = max(a[i - 1] * b[j - 1] + dp[i - 1][j - 1][0], max(dp[i - 1][j][1], dp[i][j - 1][1])); } } return max(dp[n][m][0], dp[n][m][1]); } int main() { vector< int > a = {4, -1, -3, 3}; vector< int > b = {-4, 0, 5}; int ans = MaxSOP(a, b, a.size(), b.size()); cout << ans << endl; return 0; } // This code is contributed by Tapesh(tapeshdua420) |
Java
import java.util.Arrays; public class MaxSOP { public static int maxSOP( int [] a, int [] b) { int n = a.length; int m = b.length; // Create a 3D DP table int [][][] dp = new int [n + 1 ][m + 1 ][ 2 ]; // Bottom-up approach to fill the DP table for ( int i = 0 ; i <= n; i++) { for ( int j = 0 ; j <= m; j++) { if (i == 0 || j == 0 ) { dp[i][j][ 0 ] = 0 ; dp[i][j][ 1 ] = 0 ; } else { dp[i][j][ 0 ] = Math.max( a[i - 1 ] * b[j - 1 ] + dp[i - 1 ][j - 1 ][ 1 ], Math.max(dp[i - 1 ][j][ 0 ], dp[i][j - 1 ][ 0 ])); dp[i][j][ 1 ] = Math.max( a[i - 1 ] * b[j - 1 ] + dp[i - 1 ][j - 1 ][ 0 ], Math.max(dp[i - 1 ][j][ 1 ], dp[i][j - 1 ][ 1 ])); } } } return Math.max(dp[n][m][ 0 ], dp[n][m][ 1 ]); } public static void main(String[] args) { int [] a = { 4 , - 1 , - 3 , 3 }; int [] b = { - 4 , 0 , 5 }; int ans = maxSOP(a, b); System.out.println(ans); } } |
Python3
def max_sop(a, b): n, m = len (a), len (b) # Create a 3D DP table dp = [[[ 0 , 0 ] for _ in range (m + 1 )] for _ in range (n + 1 )] # Bottom-up approach to fill the DP table for i in range ( 1 , n + 1 ): for j in range ( 1 , m + 1 ): dp[i][j][ 0 ] = max (a[i - 1 ] * b[j - 1 ] + dp[i - 1 ][j - 1 ][ 1 ], max (dp[i - 1 ][j][ 0 ], dp[i][j - 1 ][ 0 ])) dp[i][j][ 1 ] = max (a[i - 1 ] * b[j - 1 ] + dp[i - 1 ][j - 1 ][ 0 ], max (dp[i - 1 ][j][ 1 ], dp[i][j - 1 ][ 1 ])) return max (dp[n][m][ 0 ], dp[n][m][ 1 ]) # Main function a = [ 4 , - 1 , - 3 , 3 ] b = [ - 4 , 0 , 5 ] ans = max_sop(a, b) print (ans) |
C#
using System; using System.Collections.Generic; class Program { static int MaxSOP(List< int > a, List< int > b, int n, int m) { // Create a 3D DP table int [][][] dp = new int [n + 1][][]; for ( int i = 0; i <= n; i++) { dp[i] = new int [m + 1][]; for ( int j = 0; j <= m; j++) { dp[i][j] = new int [2]; dp[i][j][0] = -9999999; // Initialize as a large // negative value dp[i][j][1] = 0; } } // Bottom-up approach to fill the DP table for ( int i = 1; i <= n; i++) { for ( int j = 1; j <= m; j++) { dp[i][j][0] = Math.Max(a[i - 1] * b[j - 1] + dp[i - 1][j - 1][1], Math.Max(dp[i - 1][j][0], dp[i][j - 1][0])); dp[i][j][1] = Math.Max(a[i - 1] * b[j - 1] + dp[i - 1][j - 1][0], Math.Max(dp[i - 1][j][1], dp[i][j - 1][1])); } } return Math.Max(dp[n][m][0], dp[n][m][1]); } static void Main() { List< int > a = new List< int >{ 4, -1, -3, 3 }; List< int > b = new List< int >{ -4, 0, 5 }; int ans = MaxSOP(a, b, a.Count, b.Count); Console.WriteLine(ans); } } |
Javascript
function maxSOP(a, b) { const n = a.length; const m = b.length; // Create a 3D DP table const dp = new Array(n + 1).fill(0).map(() => new Array(m + 1).fill(0).map(() => [Number.MIN_SAFE_INTEGER, 0]) ); // Bottom-up approach to fill the DP table for (let i = 1; i <= n; i++) { for (let j = 1; j <= m; j++) { dp[i][j][0] = Math.max( a[i - 1] * b[j - 1] + dp[i - 1][j - 1][1], Math.max(dp[i - 1][j][0], dp[i][j - 1][0]) ); dp[i][j][1] = Math.max( a[i - 1] * b[j - 1] + dp[i - 1][j - 1][0], Math.max(dp[i - 1][j][1], dp[i][j - 1][1]) ); } } return Math.max(dp[n][m][0], dp[n][m][1]); } // Test the function const a = [4, -1, -3, 3]; const b = [-4, 0, 5]; const result = maxSOP(a, b); console.log(result); |
27
Time Complexity: O(N*M)
Auxiliary Space: O(N*M)
Contact Us