Maximize product of a strictly increasing or decreasing subarray | Function to find the maximum product of subarray in the array , arr [ ] ; Maximum positive product ending at the i - th index ; Minimum negative product ending at the current index ; Maximum product up to i - th index ; Check if an array element is positive or not ; Traverse the array ; If current element is positive ; Update max_ending_here ; Update min_ending_here ; Update flag ; If current element is 0 , reset the start index of subarray ; Update max_ending_here ; Update min_ending_here ; If current element is negative ; Stores max_ending_here ; Update max_ending_here ; Update min_ending_here ; Update max_so_far , if needed ; If no array elements is positive and max_so_far is 0 ; Function to find the maximum product of either increasing subarray or the decreasing subarray ; Stores start index of either increasing subarray or the decreasing subarray ; Initially assume maxProd to be 1 ; Traverse the array ; Store the longest either increasing subarray or the decreasing subarray whose start index is i ; Check for increasing subarray ; Insert elements of increasing subarray ; Check for decreasing subarray ; Insert elements of decreasing subarray ; Stores maximum subarray product of current increasing or decreasing subarray ; Update maxProd ; Update i ; Finally prmaxProd ; Driver Code
def maxSubarrayProduct ( arr , n ) : NEW_LINE INDENT max_ending_here = 1 NEW_LINE min_ending_here = 1 NEW_LINE max_so_far = 0 NEW_LINE flag = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( arr [ i ] > 0 ) : NEW_LINE INDENT max_ending_here = max_ending_here * arr [ i ] NEW_LINE min_ending_here = min ( min_ending_here * arr [ i ] , 1 ) NEW_LINE flag = 1 NEW_LINE DEDENT elif ( arr [ i ] == 0 ) : NEW_LINE INDENT max_ending_here = 1 NEW_LINE min_ending_here = 1 NEW_LINE DEDENT else : NEW_LINE INDENT temp = max_ending_here NEW_LINE max_ending_here = max ( min_ending_here * arr [ i ] , 1 ) NEW_LINE min_ending_here = temp * arr [ i ] NEW_LINE DEDENT if ( max_so_far < max_ending_here ) : NEW_LINE INDENT max_so_far = max_ending_here NEW_LINE DEDENT DEDENT if ( flag == 0 and max_so_far == 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT return max_so_far NEW_LINE DEDENT def findMaxProduct ( a , n ) : NEW_LINE INDENT i = 0 NEW_LINE maxProd = - 10 ** 9 NEW_LINE while ( i < n ) : NEW_LINE INDENT v = [ ] NEW_LINE v . append ( a [ i ] ) NEW_LINE if i < n - 1 and a [ i ] < a [ i + 1 ] : NEW_LINE INDENT while ( i < n - 1 and a [ i ] < a [ i + 1 ] ) : NEW_LINE INDENT v . append ( a [ i + 1 ] ) NEW_LINE i += 1 NEW_LINE DEDENT DEDENT elif ( i < n - 1 and a [ i ] > a [ i + 1 ] ) : NEW_LINE INDENT while ( i < n - 1 and a [ i ] > a [ i + 1 ] ) : NEW_LINE INDENT v . append ( a [ i + 1 ] ) NEW_LINE i += 1 NEW_LINE DEDENT DEDENT prod = maxSubarrayProduct ( v , len ( v ) ) NEW_LINE maxProd = max ( maxProd , prod ) NEW_LINE i += 1 NEW_LINE DEDENT return maxProd NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 2 , 10 , 8 , 1 , 100 , 101 ] NEW_LINE N = len ( arr ) NEW_LINE print ( findMaxProduct ( arr , N ) ) NEW_LINE DEDENT