<s> """<STR_LIT>""" <EOL> __author__ = '<STR_LIT>' <EOL> class Solution ( object ) : <EOL> def maxProduct_oneline ( self , nums ) : <EOL> return max ( reduce ( lambda A , n : [ max ( A ) , min ( n , A [ <NUM_LIT:1> ] * n , A [ <NUM_LIT:2> ] * n ) , max ( n , A [ <NUM_LIT:1> ] * n , A [ <NUM_LIT:2> ] * n ) ] , nums [ <NUM_LIT:1> : ] , [ nums [ <NUM_LIT:0> ] ] * <NUM_LIT:3> ) ) <EOL> def maxProduct ( self , nums ) : <EOL> """<STR_LIT>""" <EOL> small = nums [ <NUM_LIT:0> ] <EOL> large = nums [ <NUM_LIT:0> ] <EOL> maxa = nums [ <NUM_LIT:0> ] <EOL> for a in nums [ <NUM_LIT:1> : ] : <EOL> small , large = min ( a , small * a , large * a ) , max ( a , small * a , large * a ) <EOL> maxa = max ( maxa , small , large ) <EOL> return maxa <EOL> def maxProduct_error2 ( self , nums ) : <EOL> """<STR_LIT>""" <EOL> if len ( nums ) < <NUM_LIT:2> : <EOL> return max ( nums ) <EOL> n = len ( nums ) <EOL> F_pos = [ <NUM_LIT:0> for _ in xrange ( n + <NUM_LIT:1> ) ] <EOL> F_neg = [ <NUM_LIT:0> for _ in xrange ( n + <NUM_LIT:1> ) ] <EOL> maxa = <NUM_LIT:1> <EOL> for i in xrange ( <NUM_LIT:1> , n + <NUM_LIT:1> ) : <EOL> v = nums [ i - <NUM_LIT:1> ] <EOL> if v > <NUM_LIT:0> : <EOL> F_pos [ i ] = F_pos [ i - <NUM_LIT:1> ] * v if F_pos [ i - <NUM_LIT:1> ] != <NUM_LIT:0> else v <EOL> F_neg [ i ] = F_neg [ i - <NUM_LIT:1> ] * v <EOL> elif v == <NUM_LIT:0> : <EOL> F_pos [ i ] , F_neg [ i ] = <NUM_LIT:0> , <NUM_LIT:0> <EOL> else : <EOL> F_neg [ i ] = min ( <NUM_LIT:0> , F_pos [ i - <NUM_LIT:1> ] * v ) <EOL> F_pos [ i ] = max ( <NUM_LIT:0> , F_neg [ i - <NUM_LIT:1> ] * v ) <EOL> maxa = max ( maxa , F_pos [ i ] ) <EOL> return maxa <EOL> def maxProduct_error ( self , A ) : <EOL> """<STR_LIT>""" <EOL> if not A : <EOL> return <EOL> length = len ( A ) <EOL> if length == <NUM_LIT:1> : <EOL> return A [ <NUM_LIT:0> ] <EOL> dp = [ - <NUM_LIT:1> for _ in xrange ( length + <NUM_LIT:1> ) ] <EOL> dp [ length ] = <NUM_LIT:0> <EOL> for i in xrange ( length - <NUM_LIT:1> , - <NUM_LIT:1> , - <NUM_LIT:1> ) : <EOL> if A [ i ] < <NUM_LIT:0> : <EOL> dp [ i ] = dp [ i + <NUM_LIT:1> ] + <NUM_LIT:1> <EOL> elif A [ i ] == <NUM_LIT:0> : <EOL> dp [ i ] = <NUM_LIT:0> <EOL> else : <EOL> dp [ i ] = dp [ i + <NUM_LIT:1> ] <EOL> global_max = - <NUM_LIT:1> << <NUM_LIT:32> <EOL> cur = <NUM_LIT:0> <EOL> for ind , val in enumerate ( A ) : <EOL> if cur != <NUM_LIT:0> : <EOL> cur *= val <EOL> else : <EOL> cur = val <EOL> if cur < <NUM_LIT:0> and dp [ ind + <NUM_LIT:1> ] < <NUM_LIT:1> : <EOL> cur = <NUM_LIT:0> <EOL> global_max = max ( global_max , cur ) <EOL> return global_max <EOL> def maxProduct_dp ( self , A ) : <EOL> """<STR_LIT>""" <EOL> if not A : <EOL> return <EOL> length = len ( A ) <EOL> if length == <NUM_LIT:1> : <EOL> return A [ <NUM_LIT:0> ] <EOL> dp = [ - <NUM_LIT:1> for _ in xrange ( length + <NUM_LIT:1> ) ] <EOL> dp [ length ] = <NUM_LIT:0> <EOL> for i in xrange ( length - <NUM_LIT:1> , - <NUM_LIT:1> , - <NUM_LIT:1> ) : <EOL> if A [ i ] < <NUM_LIT:0> : <EOL> dp [ i ] = dp [ i + <NUM_LIT:1> ] + <NUM_LIT:1> <EOL> elif A [ i ] == <NUM_LIT:0> : <EOL> dp [ i ] = <NUM_LIT:0> <EOL> else : <EOL> dp [ i ] = dp [ i + <NUM_LIT:1> ] <EOL> global_max = - <NUM_LIT:1> << <NUM_LIT:32> <EOL> cur = <NUM_LIT:0> <EOL> start_ptr = <NUM_LIT:0> <EOL> end_ptr = <NUM_LIT:0> <EOL> while end_ptr < length : <EOL> if cur != <NUM_LIT:0> : <EOL> cur *= A [ end_ptr ] <EOL> else : <EOL> cur = A [ end_ptr ] <EOL> start_ptr = end_ptr <EOL> end_ptr += <NUM_LIT:1> <EOL> if cur < <NUM_LIT:0> and dp [ end_ptr ] < <NUM_LIT:1> : <EOL> while start_ptr <= end_ptr and A [ start_ptr ] > <NUM_LIT:0> : <EOL> cur /= A [ start_ptr ] <EOL> start_ptr += <NUM_LIT:1> <EOL> if A [ start_ptr ] < <NUM_LIT:0> : <EOL> cur /= A [ start_ptr ] <EOL> start_ptr += <NUM_LIT:1> <EOL> if start_ptr == end_ptr : <EOL> cur = <NUM_LIT:0> <EOL> global_max = max ( global_max , cur ) <EOL> return global_max <EOL> if __name__ == "<STR_LIT:__main__>" : <EOL> print Solution ( ) . maxProduct ( [ <NUM_LIT:2> , <NUM_LIT:3> , - <NUM_LIT:2> , <NUM_LIT:4> ] ) <EOL> assert Solution ( ) . maxProduct ( [ <NUM_LIT:2> , - <NUM_LIT:5> , - <NUM_LIT:2> , - <NUM_LIT:4> , <NUM_LIT:3> ] ) == <NUM_LIT> <EOL> assert Solution ( ) . maxProduct ( [ - <NUM_LIT:2> , <NUM_LIT:0> , - <NUM_LIT:1> ] ) == <NUM_LIT:0> <EOL> assert Solution ( ) . maxProduct ( [ - <NUM_LIT:2> ] ) == - <NUM_LIT:2> <EOL> assert Solution ( ) . maxProduct ( [ <NUM_LIT:2> , <NUM_LIT:3> , - <NUM_LIT:2> , <NUM_LIT:4> , - <NUM_LIT:2> ] ) == <NUM_LIT> <EOL> assert Solution ( ) . maxProduct ( [ <NUM_LIT:2> , <NUM_LIT:3> , - <NUM_LIT:2> , <NUM_LIT:4> , <NUM_LIT:0> , - <NUM_LIT:2> ] ) == <NUM_LIT:6> <EOL> assert Solution ( ) . maxProduct ( [ <NUM_LIT:2> , <NUM_LIT:3> , - <NUM_LIT:2> , <NUM_LIT:4> ] ) == <NUM_LIT:6> </s>
