Максимални производни подниз | Сет 2 (користећи два преласка)
Дати низ који садржи и позитивне и негативне целе бројеве пронађите производ максималног подниза производа. Очекивана временска сложеност је О(н) и може се користити само О(1) додатног простора.
Примери:
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. Разговарали смо о решењу овог проблема овде .
У овом посту се говори о занимљивом решењу. Идеја је заснована на чињеници да је укупан максимални производ највише од следећа два:
- Максимални производ у кретању са лева на десно.
- Максимални производ у кретању здесна налево
На пример, размотрите горњи трећи узорак уноса {-1 -2 -3 4}. Ако пређемо низ само у правцу унапред (сматрајући -1 као део излаза) максимални производ ће бити 2. Ако пређемо низ у правцу уназад (сматрајући 4 као део излаза) максимални производ ће бити 24, тј.; { -2 -3 4}.
Једна важна ствар је руковање 0. Морамо да израчунамо нови збир унапред (или уназад) кад год видимо 0.
Испод је имплементација горње идеје:
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>
Излаз
24
Временска сложеност: О(н)
Помоћни простор : О(1)
Имајте на уму да горње решење захтева два обиласка низа док је претходно решење захтева само једно обилажење.
