leetcode 152. Maximum Product Subarray (最大连续子序列乘积,dp)

2017年4月14日 0 作者 CrazyKK

 

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.

思路:由于有正,有负,还有0.。。所以比最大子串之和要复杂一些。。。

dp[i].max表示到当前位置的最大乘积。

dp[i].min表示到当前位置的最小乘积。

dp[i].max = max{dp[i-1].max*a[i],dp[i-1].min*a[i],a[i]};

dp[i].min同理

边界dp[i].max = dp[i].min = a[0]