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"
原文：http://www.cnblogs.com/tonix/p/3995924.html