动态规划,思路同子数组最大乘积(全为正数)一样,dp[i][0]代表当前以arr[i]结尾的最大乘积正数,dp[i][1]为最小乘积负数。
转移方程:
1.当arr[i]>0时:
dp[i][0]=max(dp[i-1][0]arr[i],arr[i]),dp[i][1]=dp[i-1][1]arr[i].
2.当arr[i]==0,dp[i][0]=dp[i[1]=0.
3.当arr[i]<0时,dp[i][0]=dp[i-1][]arr[i].dp[i][1]=min(dp[i-1][0]arr[i]).
边界条件: dp[-1][0]=-1,dp[-1][1]=1,最后同步更新ans即可。
class Solution {
public:
double maxProduct(vector<double> arr) {
vector<vector<double>> dp(arr.size()+1,vector<double>(2,0));
dp[0][0]=-1;
dp[0][1]=1;
double ans=-3000000.0;
for (int i=1;i<=arr.size();++i){
if (arr[i-1]<0){
dp[i][0]=dp[i-1][1]arr[i-1];
dp[i][1]=min(dp[i-1][0]
arr[i-1],arr[i-1]);
}
else if (arr[i-1]==0){
dp[i][0]=0;
dp[i][1]=0;
}
else{
dp[i][0]=max(dp[i-1][0]arr[i-1],arr[i-1]);
dp[i][1]=dp[i-1][1]
arr[i-1];
}
ans=max(ans,dp[i][0]);
}
return ans;
}
};</double></double></double>