Question: https://oj.leetcode.com/problems/maximum-product-subarray/
Question Name: Maximum Product Subarray
The following solution is not the optimal. Because the recursion is not necessary. But recursion does make the coding easier.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | class Solution: # @param A, a list of non-zero integers # @return an integer def maxProductWithoutZero(self, A): # Two base cases for this recursive method. if len(A) == 0: return 0 if len(A) == 1: return A[0] negativeCount = len([i for i in A if i < 0]) if negativeCount % 2 == 0: # There are even number of negative integers. The product of all them # is a positive integer as the maximum product among all subarrays. return reduce(lambda x, y: x * y, A, 1) else: # There are odd number of negative integers. We divide the array into # two subarray: one without the first negative integer, and the other # without the last negative integer. firstNeg = 0 while firstNeg < len(A): if A[firstNeg] < 0: break firstNeg += 1 lastNeg = len(A) - 1 while lastNeg >= 0: if A[lastNeg] < 0: break lastNeg -= 1 return max(self.maxProductWithoutZero(A[:lastNeg]), self.maxProductWithoutZero(A[firstNeg + 1:])) # @param A, a list of integers # @return an integer def maxProduct(self, A): begin, end = 0, 0 if A.count(0) != 0: maxProd = 0 else: maxProd = A[0] # Use 0 (zero) as delimiter to split the original array into small ones, # which do not contain 0. while end < len(A): if A[end] != 0: end += 1 else: maxProd = max(maxProd, self.maxProductWithoutZero(A[begin : end])) end += 1 begin = end return max(maxProd, self.maxProductWithoutZero(A[begin : end])) |