# Leetcode 152 - Maximum product subarray

Note:

• Use normal memory will cause TLE because the array can get really big.
• The tricky thing about product is that if dp[i-1] is really negative and really small, but nums[i] < 0. It might even be the max that we want.
• So, we not only need to record max from 0 to i - 1, but also min!!
• Define dp[i][0] as the MIN product ending with nums[i].
• dp[i][1] as the MAX product ending with nums[i].
• It’s also easy to get:
• dp[i][0] = Math.min(nums[i], dp[i - 1][0]*nums[i], dp[i - 1][1]*nums[i]).
• dp[i][1] = Math.max(nums[i], dp[i - 1][0]*nums[i], dp[i - 1][1]*nums[i]).

Question:

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

It is guaranteed that the answer will fit in a 32-bit integer.

A subarray is a contiguous subsequence of the array.

Example:

Code:
DP O(n)

Brute Force - Heap out of memory when nums is too long