Maksimal produktundergruppe | Sett 2 (bruker to traverseringer)
Gitt en matrise som inneholder både positive og negative heltall, finn produktet av den maksimale produktundermatrisen. Forventet tidskompleksitet er O(n) og kun O(1) ekstra plass kan brukes.
Eksempler:
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 diskutert en løsning på dette problemet her .
I dette innlegget diskuteres en interessant løsning. Ideen er basert på det faktum at det totale maksimale produktet er maksimalt følgende to:
- Maksimalt produkt i kryss fra venstre til høyre.
- Maksimalt produkt i kryss fra høyre til venstre
Tenk for eksempel på den tredje eksempelinngangen ovenfor {-1 -2 -3 4}. Hvis vi krysser matrisen bare i retning fremover (vurderer -1 som en del av output) vil maksimalt produkt være 2. Hvis vi traverserer matrisen i retning bakover (vurderer 4 som en del av output) vil maksimalt produkt være 24 dvs.; { -2 -3 4}.
En viktig ting er å håndtere 0-tallet. Vi må beregne ny sum forover (eller bakover) når vi ser 0.
Nedenfor er implementeringen av ideen ovenfor:
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>
Produksjon
24
Tidskompleksitet: O(n)
Hjelpeområde: O(1)
Merk at løsningen ovenfor krever to traverseringer av en matrise mens tidligere løsning krever kun én gjennomkjøring.
![Java main() Metode – offentlig statisk void main(String[] args)](https://techcodeview.com/img/java-basics/92/java-main-method-public-static-void-main.webp)
