Maximize product of same | C ++ implementation to maximize product of same - indexed elements of same size subsequences ; Utility function to find the maximum ; Utility function to find the maximum scalar product from the equal length sub - sequences taken from the two given array ; Return a very small number if index is invalid ; If the sub - problem is already evaluated , then return it ; Take the maximum of all the recursive cases ; Function to find maximum scalar product from same size sub - sequences taken from the two given array ; Initialize a 2 - D array for memoization ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define INF  10000000 NEW_LINE int maximum ( int A , int B , int C , int D ) { return max ( max ( A , B ) , max ( C , D ) ) ; } int maxProductUtil ( int X , int Y , int * A , int * B , vector < vector < int > > & dp ) { if ( X < 0 or Y < 0 ) return - INF ; if ( dp [ X ] [ Y ] != -1 ) return dp [ X ] [ Y ] ; 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 ] ; } int maxProduct ( int A [ ] , int N , int B [ ] , int M ) { vector < vector < int > > dp ( N , vector < int > ( M , -1 ) ) ; return maxProductUtil ( N - 1 , M - 1 , A , B , dp ) ; } int 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 ) ; }