# 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:`

1 | Input: nums = [2,3,-2,4] |

`Code:`

`DP O(n)`

1 | /** |

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

1 | /** |