首页 > 代码库 > LeetCode "Maximum Product Subarray"
LeetCode "Maximum Product Subarray"
Intuitively there must a O(n) solution.
First I tried a bottom-up DP solution but it had a TLE:
class Solution {public: int maxProduct(int A[], int n) { vector<int> dp;dp.resize(n); dp.assign(A, A + n); int max = *std::max_element(A, A + n); for (size_t len = 2; len <= n; len ++) for (int i = 0; i <= n - len; i ++) { dp[i] *= A[i + len - 1]; max = std::max(max, dp[i]); } return max; }};
So what is O(n) solution then? The idea is to keep track of 2 lines: one for positive and one for negative. Inspired by:
https://oj.leetcode.com/discuss/11923/sharing-my-solution-o-1-space-o-n-running-time
LeetCode "Maximum Product Subarray"
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。