Maximal Product Subarray | Set 2 (med två genomgångar)
Med tanke på en matris som innehåller både positiva och negativa heltal, hitta produkten av den maximala produktundermatrisen. Förväntad tidskomplexitet är O(n) och endast O(1) extra utrymme kan användas.
Exempel:
Input: arr[] = {6 -3 -10 0 2} Output: 180 // The subarray is {6 -3 -10} Input: arr[] = {-1 -3 -10 0 60} Output: 60 // The subarray is {60} Input: arr[] = {-1 -2 -3 4} Output: 24 // The subarray is {-2 -3 4} Input: arr[] = {-10} Output: 0 // An empty array is also subarray // and product of empty subarray is // considered as 0. Vi har diskuterat en lösning på detta problem här .
I det här inlägget diskuteras en intressant lösning. Idén bygger på det faktum att den totala maximala produkten är maximalt följande två:
- Maximal produkt från vänster till höger.
- Maximal produkt i höger till vänster traversering
Betrakta till exempel ovanstående tredje exempelindata {-1 -2 -3 4}. Om vi korsar matrisen endast i riktning framåt (med tanke på -1 som en del av output) kommer maximal produkt att vara 2. Om vi korsar matrisen i riktning bakåt (med tanke på 4 som en del av output) kommer maximal produkt att vara 24, dvs. { -2 -3 4}.
En viktig sak är att hantera 0:or. Vi måste beräkna ny summa framåt (eller bakåt) när vi ser 0.
Nedan är implementeringen av ovanstående idé:
C++ // C++ program to find maximum product subarray #include using namespace std ; // Function for maximum product int max_product ( int arr [] int n ) { // Initialize maximum products in forward and // backward directions int max_fwd = INT_MIN max_bkd = INT_MIN ; // Initialize current product int max_till_now = 1 ; //check if zero is present in an array or not bool isZero = false ; // max_fwd for maximum contiguous product in // forward direction // max_bkd for maximum contiguous product in // backward direction // iterating within forward direction in array for ( int i = 0 ; i < n ; i ++ ) { // if arr[i]==0 it is breaking condition // for contiguous subarray max_till_now = max_till_now * arr [ i ]; if ( max_till_now == 0 ) { isZero = true ; max_till_now = 1 ; continue ; } if ( max_fwd < max_till_now ) // update max_fwd max_fwd = max_till_now ; } max_till_now = 1 ; // iterating within backward direction in array for ( int i = n -1 ; i >= 0 ; i -- ) { max_till_now = max_till_now * arr [ i ]; if ( max_till_now == 0 ) { isZero = true ; max_till_now = 1 ; continue ; } // update max_bkd if ( max_bkd < max_till_now ) max_bkd = max_till_now ; } // return max of max_fwd and max_bkd int res = max ( max_fwd max_bkd ); // Product should not be negative. // (Product of an empty subarray is // considered as 0) if ( isZero ) return max ( res 0 ); return res ; } // Driver Program to test above function int main () { int arr [] = { -1 -2 -3 4 }; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); cout < < max_product ( arr n ) < < endl ; return 0 ; }
Java // Java program to find // maximum product subarray import java.io.* ; class GFG { // Function for maximum product static int max_product ( int arr [] int n ) { // Initialize maximum products in // forward and backward directions int max_fwd = Integer . MIN_VALUE max_bkd = Integer . MIN_VALUE ; //check if zero is present in an array or not boolean isZero = false ; // Initialize current product int max_till_now = 1 ; // max_fwd for maximum contiguous // product in forward direction // max_bkd for maximum contiguous // product in backward direction // iterating within forward // direction in array for ( int i = 0 ; i < n ; i ++ ) { // if arr[i]==0 it is breaking // condition for contiguous subarray max_till_now = max_till_now * arr [ i ] ; if ( max_till_now == 0 ) { isZero = true ; max_till_now = 1 ; continue ; } // update max_fwd if ( max_fwd < max_till_now ) max_fwd = max_till_now ; } max_till_now = 1 ; // iterating within backward // direction in array for ( int i = n - 1 ; i >= 0 ; i -- ) { max_till_now = max_till_now * arr [ i ] ; if ( max_till_now == 0 ) { isZero = true ; max_till_now = 1 ; continue ; } // update max_bkd if ( max_bkd < max_till_now ) max_bkd = max_till_now ; } // return max of max_fwd and max_bkd int res = Math . max ( max_fwd max_bkd ); // Product should not be negative. // (Product of an empty subarray is // considered as 0) if ( isZero ) return Math . max ( res 0 ); return res ; } // Driver Code public static void main ( String [] args ) { int arr [] = { - 1 - 2 - 3 4 }; int n = arr . length ; System . out . println ( max_product ( arr n ) ); } } // This code is contributed by anuj_67.
Python3 # Python3 program to find # maximum product subarray import sys # Function for maximum product def max_product ( arr n ): # Initialize maximum products # in forward and backward directions max_fwd = - sys . maxsize - 1 max_bkd = - sys . maxsize - 1 #check if zero is present in an array or not isZero = False ; # Initialize current product max_till_now = 1 # max_fwd for maximum contiguous # product in forward direction # max_bkd for maximum contiguous # product in backward direction # iterating within forward # direction in array for i in range ( n ): # if arr[i]==0 it is breaking # condition for contiguous subarray max_till_now = max_till_now * arr [ i ] if ( max_till_now == 0 ): isZero = True max_till_now = 1 ; continue if ( max_fwd < max_till_now ): #update max_fwd max_fwd = max_till_now max_till_now = 1 # iterating within backward # direction in array for i in range ( n - 1 - 1 - 1 ): max_till_now = max_till_now * arr [ i ] if ( max_till_now == 0 ): isZero = True max_till_now = 1 continue # update max_bkd if ( max_bkd < max_till_now ) : max_bkd = max_till_now # return max of max_fwd and max_bkd res = max ( max_fwd max_bkd ) # Product should not be negative. # (Product of an empty subarray is # considered as 0) if isZero == True : return max ( res 0 ) return res # Driver Code arr = [ - 1 - 2 - 3 4 ] n = len ( arr ) print ( max_product ( arr n )) # This code is contributed # by Yatin Gupta
C# // C# program to find maximum product // subarray using System ; class GFG { // Function for maximum product static int max_product ( int [] arr int n ) { // Initialize maximum products in // forward and backward directions int max_fwd = int . MinValue max_bkd = int . MinValue ; // Initialize current product int max_till_now = 1 ; // max_fwd for maximum contiguous // product in forward direction // max_bkd for maximum contiguous // product in backward direction // iterating within forward // direction in array for ( int i = 0 ; i < n ; i ++ ) { // if arr[i]==0 it is breaking // condition for contiguous subarray max_till_now = max_till_now * arr [ i ]; if ( max_till_now == 0 ) { max_till_now = 1 ; continue ; } // update max_fwd if ( max_fwd < max_till_now ) max_fwd = max_till_now ; } max_till_now = 1 ; // iterating within backward // direction in array for ( int i = n - 1 ; i >= 0 ; i -- ) { max_till_now = max_till_now * arr [ i ]; if ( max_till_now == 0 ) { max_till_now = 1 ; continue ; } // update max_bkd if ( max_bkd < max_till_now ) max_bkd = max_till_now ; } // return max of max_fwd and max_bkd int res = Math . Max ( max_fwd max_bkd ); // Product should not be negative. // (Product of an empty subarray is // considered as 0) return Math . Max ( res 0 ); } // Driver Code public static void Main () { int [] arr = { - 1 - 2 - 3 4 }; int n = arr . Length ; Console . Write ( max_product ( arr n ) ); } } // This code is contributed by nitin mittal.
PHP // PHP program to find maximum // product subarray // Function for maximum product function max_product ( $arr $n ) { // Initialize maximum products // in forward and backward // directions $max_fwd = PHP_INT_MIN ; $max_bkd = PHP_INT_MIN ; // Initialize current product $max_till_now = 1 ; // max_fwd for maximum contiguous // product in forward direction // max_bkd for maximum contiguous // product in backward direction // iterating within forward direction // in array for ( $i = 0 ; $i < $n ; $i ++ ) { // if arr[i]==0 it is // breaking condition // for contiguous subarray $max_till_now = $max_till_now * $arr [ $i ]; if ( $max_till_now == 0 ) { $max_till_now = 1 ; continue ; } // update max_fwd if ( $max_fwd < $max_till_now ) $max_fwd = $max_till_now ; } $max_till_now = 1 ; // iterating within backward // direction in array for ( $i = $n - 1 ; $i >= 0 ; $i -- ) { $max_till_now = $max_till_now * $arr [ $i ]; if ( $max_till_now == 0 ) { $max_till_now = 1 ; continue ; } // update max_bkd if ( $max_bkd < $max_till_now ) $max_bkd = $max_till_now ; } // return max of max_fwd // and max_bkd $res = max ( $max_fwd $max_bkd ); // Product should not be negative. // (Product of an empty subarray is // considered as 0) return max ( $res 0 ); } // Driver Code $arr = array ( - 1 - 2 - 3 4 ); $n = count ( $arr ); echo max_product ( $arr $n ); // This code is contributed by anuj_67. ?>
JavaScript < script > // JavaScript program to find maximum product // subarray // Function for maximum product function max_product ( arr n ) { // Initialize maximum products in // forward and backward directions let max_fwd = Number . MIN_VALUE max_bkd = Number . MIN_VALUE ; // Initialize current product let max_till_now = 1 ; // max_fwd for maximum contiguous // product in forward direction // max_bkd for maximum contiguous // product in backward direction // iterating within forward // direction in array for ( let i = 0 ; i < n ; i ++ ) { // if arr[i]==0 it is breaking // condition for contiguous subarray max_till_now = max_till_now * arr [ i ]; if ( max_till_now == 0 ) { max_till_now = 1 ; continue ; } // update max_fwd if ( max_fwd < max_till_now ) max_fwd = max_till_now ; } max_till_now = 1 ; // iterating within backward // direction in array for ( let i = n - 1 ; i >= 0 ; i -- ) { max_till_now = max_till_now * arr [ i ]; if ( max_till_now == 0 ) { max_till_now = 1 ; continue ; } // update max_bkd if ( max_bkd < max_till_now ) max_bkd = max_till_now ; } // return max of max_fwd and max_bkd let res = Math . max ( max_fwd max_bkd ); // Product should not be negative. // (Product of an empty subarray is // considered as 0) return Math . max ( res 0 ); } let arr = [ - 1 - 2 - 3 4 ]; let n = arr . length ; document . write ( max_product ( arr n ) ); < /script>
Produktion
24
Tidskomplexitet: O(n)
Hjälputrymme: O(1)
Observera att ovanstående lösning kräver två genomgångar av en array medan tidigare lösning kräver endast en genomgång.
