Wednesday, October 8, 2014

Leetcode: Maximum Product Subarray @Python

Dynamic Programming, O(n) time complexity and O(1) space complexity.
Scan the list once,keep updating two variables mincrt and maxcrt.
mincrt is the minimum product end with the last element scanned. maxcrt is the maximum counterpart.
rst is used to store the maximal product so far.
Every time when updating with the new element, mincrt and maxcrt are from either the product with the new element ,or breaking up multiplication and starting from the new element.
class Solution:
    # @param A, a list of integers
    # @return an integer
    def maxProduct(self, A):
        mincrt=maxcrt=rst=A[0]
        for i in range(1,len(A)):
            mincrt,maxcrt=min(A[i],A[i]*mincrt,A[i]*maxcrt),max(A[i],A[i]*mincrt,A[i]*maxcrt)
            rst=max(rst,maxcrt)
        return rst

No comments :

Post a Comment