Maximální produkt Subarray | Sada 2 (pomocí dvou přechodů)
Dané pole, které obsahuje kladná i záporná celá čísla, najděte součin maximálního podpole součinu. Očekávaná časová složitost je O(n) a lze použít pouze O(1) prostor navíc.
Příklady:
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. Diskutovali jsme o řešení tohoto problému zde .
V tomto příspěvku je diskutováno zajímavé řešení. Myšlenka je založena na skutečnosti, že celkový maximální produkt je maximálně z následujících dvou:
- Maximální produkt v pojezdu zleva doprava.
- Maximální produkt v pojezdu zprava doleva
Uvažujme například výše uvedený třetí vzorový vstup {-1 -2 -3 4}. Pokud pole projíždíme pouze v dopředném směru (uvažujeme -1 jako součást výstupu), maximální součin bude 2. Pokud pole projíždíme ve zpětném směru (uvažujeme-li 4 jako součást výstupu), maximální součin bude 24 tj.; { -2 -3 4}.
Jedna důležitá věc je zvládnout nuly. Musíme vypočítat nový dopředný (nebo zpětný) součet, kdykoli vidíme 0.
Níže je uvedena implementace výše uvedené myšlenky:
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>
Výstup
24
Časová složitost: O(n)
Pomocný prostor: O(1)
Všimněte si, že výše uvedené řešení vyžaduje dva průchody polem, zatímco předchozí řešení vyžaduje pouze jeden průchod.
