• Time:O(n)
• Space:O(1)

## C++

``````class Solution {
public:
int maxProduct(vector<int>& nums) {
int ans = nums[0];
int dpMin = nums[0];  // min so far
int dpMax = nums[0];  // max so far

for (int i = 1; i < nums.size(); ++i) {
const int num = nums[i];
const int prevMin = dpMin;  // dpMin[i - 1]
const int prevMax = dpMax;  // dpMax[i - 1]
if (num < 0) {
dpMin = min(prevMax * num, num);
dpMax = max(prevMin * num, num);
} else {
dpMin = min(prevMin * num, num);
dpMax = max(prevMax * num, num);
}
ans = max(ans, dpMax);
}

return ans;
}
};
``````

## JAVA

``````class Solution {
public int maxProduct(int[] nums) {
int ans = nums[0];
int dpMin = nums[0]; // min so far
int dpMax = nums[0]; // max so far

for (int i = 1; i < nums.length; ++i) {
final int num = nums[i];
final int prevMin = dpMin; // dpMin[i - 1]
final int prevMax = dpMax; // dpMax[i - 1]
if (num < 0) {
dpMin = Math.min(prevMax * num, num);
dpMax = Math.max(prevMin * num, num);
} else {
dpMin = Math.min(prevMin * num, num);
dpMax = Math.max(prevMax * num, num);
}
ans = Math.max(ans, dpMax);
}

return ans;
}
}
``````

## Python

``````class Solution:
def maxProduct(self, nums: List[int]) -> int:
ans = nums[0]
prevMin = nums[0]
prevMax = nums[0]

for i in range(1, len(nums)):
mini = prevMin * nums[i]
maxi = prevMax * nums[i]
prevMin = min(nums[i], mini, maxi)
prevMax = max(nums[i], mini, maxi)
ans = max(ans, prevMax)

return ans
``````