O(n) Time, O(1) space solution within one scan

  • 2

    Using dp and keep a record of current max product together with current min product.

    class Solution:
        # @param {integer[]} nums
        # @return {integer}
        def maxProduct(self, nums):
            i = 0
            currentMax, currentMin, ans = nums[0], nums[0], nums[0]
            for i in range(1, len(nums)):
                n = nums[i]
                tmp = currentMax
                currentMax = max(n, n*currentMax, n*currentMin)
                currentMin = min(n, n*tmp, n*currentMin)
                ans = max(ans, currentMax)
            return ans

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.