Maximum product subarray#

1Input: [2,3,-2,4]
2Output: 6
3Explanation: [2,3] has the largest product 6.

1Input: [-2,0,-1]
2Output: 0
3Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

 1class Solution(object):
 2    def maxProduct(self, nums):
 3        """
 4        :type nums: List[int]
 5        :rtype: int
 6        """
 7        if not nums:
 8            return 0
 9        best = nums[0]
10        current_max = nums[0]
11        current_min = nums[0]
12        for x in range(1, len(nums)):
13            n = (nums[x], nums[x] * current_max, nums[x] * current_min)
14            current_max = max(n)
15            current_min = min(n)
16            best = max(current_max, best)
17            print(nums[x], current_max, current_min, best)
18        return best
19
20
21in_arrs = [
22    # [2, 1, 2, 1, 0, 1, 2],
23    # [3, 3, 5, 0, 0, 3, 1, 4],
24    # [3, 5, 0, 1, 4],
25    # [1, 2, -1, 1],
26    # [1, 2, 3, 4],
27    # [1, 1, 1, 3, 3, 4, 3, 2, 4, 2],
28    # [-2, 1, -3, 4, -1, 2, 1, -5, 4],
29    [2, 3, -2, 4],
30    [-2, 0, -1],
31    [-2],
32    [-4, -3],
33    [-2, 3, -4],
34    [2, -3, 4],
35    [0, -2, -3],
36    [0, -2],
37    [2, -3, 4, 0],
38    [2, -5, -2, -4, 3],
39]
40
41if __name__ == "__main__":
42
43    sol = Solution()
44    for nin in in_arrs:
45        print(nin)
46        r = sol.maxProduct(nin)
47        print(r)