Maximum Product Subarray

就是简单的dp问题。

class Solution:
    def maxProduct(self, A):
        ps, ns = [A[0]], [A[0]]
        for i in xrange(1, len(A)):
            tp, tn = ps[-1], ns[-1]
            ps.append(max(A[i], A[i] * tp, A[i] * tn))
            ns.append(min(A[i], A[i] * tn, A[i] * tp))
        return max(ps)

damajia 发表于 2014-9-25 02:59
就是普通的 DP 不明白为什么写这么长

你写的答案错了，自己到leetcodeOJ上提交一遍，自己在看看吧

O(n)的，想法是最大值 = 最小负值 * 最小负值，或者是最大正值 * 最大正值。最小负值 = 最大正值 * 最小负值

1. class Solution {
   
2. public:
   
3.     int maxProduct(int A[], int n) {
   
4.         vector<int> maxdp(n), mindp(n);
   
5.         
   
6.         maxdp[0] = mindp[0] = A[0];
   
7.         int maxv = maxdp[0];
   
8.         for (int i = 1; i < n; i++) {
   
9.             maxdp[i] = max(mindp[i - 1] * A[i], maxdp[i - 1] * A[i]);
   
10.             maxdp[i] = max(maxdp[i], A[i]);
    
11.             mindp[i] = min(mindp[i - 1] * A[i], maxdp[i - 1] * A[i]);
    
12.             mindp[i] = min(mindp[i], A[i]);
    
13.             maxv = max(maxv, maxdp[i]);
    
14.         }
    
15.         return maxv;
    
16.     }
    
17. };

复制代码

quan1614 发表于 2014-11-17 20:02
你写的答案错了，自己到leetcodeOJ上提交一遍，自己在看看吧

我觉得他写的是对的啊。同时保存局部最小和最大，保存最小是用乘法的负负得正的规律决定的。

chong 发表于 2014-12-23 20:28
我觉得他写的是对的啊。同时保存局部最小和最大，保存最小是用乘法的负负得正的规律决定的。

maxProduct要求是连续的，它只保留了历史上最大最小的，没有保留当前临时最大最小的。
或者简单点说，这种做法不能保证得到的是连续区间的，所以错了
我邮箱 dongjiaquan89@gmail.com 可以私下说

O(N) algorithm:

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        if(n<=0) return 0;
        int ret, curMax, curMin;
        ret = curMax = curMin = nums[0];
        for(int i=1; i<n; i++) {
            int temp = curMax;
            curMax = max(max(curMax*nums[i], curMin*nums[i]),nums[i]);
            curMin = min(min(temp*nums[i], curMin*nums[i]),nums[i]);
            ret = max(ret, curMax);
        }
        return ret;
    }
};