#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/dynamic-programming-fundamentals/maximum-product-implement-solution

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/dynamic-programming-fundamentals/maximum-product-implement-solution

Repovive

LeetCode 152 Maximum Product Subarray - Implementation - Dynamic Programming Fundamentals | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units60h total

Open in Course

LeetCode 152 Maximum Product Subarray - Implementation

function maxProduct(nums)
    n := length of nums
    maxProd := nums[0]
    minProd := nums[0]
    result := nums[0]
    for i from 1 to n - 1
        if nums[i] < 0
            swap(maxProd, minProd)
        maxProd := max(nums[i], maxProd * nums[i])
        minProd := min(nums[i], minProd * nums[i])
        result := max(result, maxProd)
    return result

The swap handles the sign flip elegantly. When $nums[i]$ is negative, what was maximum becomes minimum and vice versa. Then you apply the standard recurrence.

we only need two variables, not arrays. Each position only depends on the previous one. This is the same space reduction pattern you saw in Fibonacci and Climbing Stairs.

Time: $O(n)$ . Space: $O(1)$ .