[LeetCode] Challenge log 152

Posted on | Edited on |
152. Maximum Product Subarray

https://leetcode.com/problems/maximum-product-subarray/description/

It is a DP problem. Similar to 53.

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

Solution:

DP thought:

  • use two slot to cache the max and the min products of the subarray that ends with current pointer.
  • at each position, each time there are three possible numbers to choose from:
    • current number
    • current number X max product of last position
    • current number X min product of last position
  • so take the min and max of the three options to be current minP and maxP of current postion
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        maxP = nums[0]
        minP = nums[0]
        p = 1
        result = nums[0] 
        while p < len(nums):
            tmp1 = max(nums[p], nums[p] * maxP, nums[p] * minP)
            tmp2 = min(nums[p], nums[p] * maxP, nums[p] * minP) 
            maxP = tmp1
            minP = tmp2
            print(nums[p], maxP, minP)
            result = max(result, maxP)
            p += 1
        return result
0%