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

 

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]

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz