首页 > 代码库 > leetcode Maximum Product Subarray
leetcode Maximum Product Subarray
之前好像做过这样的，以前是加法，现在是乘法。
一开始我也傻逼得用n方的试了下，肯定是TLE的。
那显然就是可以O(n)解决了
用两个dp数组，一个存最大值，一个存最小值，因为可能是负数再乘以负数就很大了，所以每次更新需要借助最小值一同更新最大值。最后遍历一边dp大的数组就有答案了。
class Solution {public: int maxProduct(int A[], int n) { int dp[n], dpNeg[n], maximum; memset(dp, 0, sizeof(dp)); memset(dpNeg, 0, sizeof(dpNeg)); dp[0] = A[0]; dpNeg[0] = A[0]; for (int i = 1; i < n; i++) { dp[i] = max(dp[i - 1] * A[i], A[i]); dp[i] = max(dpNeg[i - 1] * A[i], dp[i]); dpNeg[i] = min(dpNeg[i - 1] * A[i], A[i]); dpNeg[i] = min(dp[i - 1] * A[i], dpNeg[i]); } for (int i = 0; i < n; i++) { if (dp[i] > maximum) maximum = dp[i]; } return maximum; }};
这题也unlock了
也可以看看Ganker的，他是在for里面就判断了maximum了。说是全局最优和局部最优的最大值。其实思路一样的吧。
leetcode Maximum Product Subarray
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。