LeetCode Q152: Maximum Product Subarray (hard)

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

Solution:

Use DP. Given an array with N integers, we can create a Nx2 table. For each 1x2 entry in the table, we keep track the largest product (most of time for positive product) and smallest product (most of time for negative product so far) met so far. So, the idea is to save all valid product met so far including the negative ones, because we don't know whether there will be more negative integer in the remaining part of the array. 

At the end of this design, we notice that, actually, there is no need to create a Nx2 table, all we need basically just two variables storing largest and smallest product obtained so far.

Round 2 solution: