Maksimum Ürün Alt Dizisi | Set 2 (İki Geçiş Kullanarak)
Hem pozitif hem de negatif tam sayılar içeren bir dizi verildiğinde, maksimum çarpım alt dizisinin çarpımını bulun. Beklenen Zaman karmaşıklığı O(n)'dir ve yalnızca O(1) ekstra alan kullanılabilir.
Örnekler:
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. Bu sorunun çözümünü tartıştık Burada .
Bu yazıda ilginç bir çözüm tartışılıyor. Fikir, genel maksimum ürünün maksimum aşağıdaki iki değer olduğu gerçeğine dayanmaktadır:
- Soldan sağa geçişte maksimum ürün.
- Sağdan sola geçişte maksimum ürün
Örneğin yukarıdaki üçüncü örnek girişi düşünün {-1 -2 -3 4}. Diziyi yalnızca ileri yönde hareket ettirirsek (çıkışın bir parçası olarak -1'i dikkate alırsak) maksimum ürün 2 olur. Diziyi geriye doğru yönde geçirirsek (çıkışın bir parçası olarak 4'ü dikkate alırsak) maksimum ürün 24 olur; { -2 -3 4}.
Önemli bir şey 0'ları ele almaktır. 0'ı gördüğümüzde yeni ileri (veya geri) toplamı hesaplamamız gerekir.
Aşağıda yukarıdaki fikrin uygulanması yer almaktadır:
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>
Çıkış
24
Zaman Karmaşıklığı : O(n)
Yardımcı Alan : O(1)
Yukarıdaki çözümün bir dizide iki geçiş gerektirdiğini unutmayın. önceki çözüm yalnızca bir geçiş gerektirir.
