# [Maximum Product Subarray](https://leetcode.com/problems/maximum-product-subarray/)
###### tags: `Leetcode`, `Medium`, `Dynamic Programming`

## Approach

* At every index position of the input array, we need to keep track of the `current_minimum` and `current_maximum`. This is because the product of two negatives is positives and the product of a positive and a negative number is negative.
* Initialize `current_minimum` and `current_maximum` to hold values `1` each.
* For every number in the input list calculate the `current_minimum`, `current_maximum` and `result` using the below formula:

    temp = max(num * curent_maximum)
    current_maximum = max(temp, num * current_minimum, num)
    current_minimum = min(temp, num * current_minimum, num)
    result = max(result, current_maximum)

* The final result is `max(result, current_maximum)`

## Asymptotic Analysis
### Time Complexity: **O(N)**
### Space Complexity: **O(1)**

## Code

from typing import List


class MaximumProductSubarray:
    def max_product(self, nums: List[int]) -> int:
        cur_min, cur_max = 1, 1
        result = nums[0]
        for num in nums:
            temp = num * cur_max
            cur_max = max(temp, num * cur_min, num)
            cur_min = min(temp, num * cur_min, num)
            result = max(result, cur_max)
        return result


input_numbers = [2, 3, 0, 3, 4]
mps = MaximumProductSubarray()
print(f"Maximum product of the input list {input_numbers} = {mps.max_product(input_numbers)}")