Maximum Product Subarray(LeetCode)

题目：

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6.

思路：

这道题的原型是求最大和的子序列，二者差别主要在于乘法和加法不太一样，如果是加法，动态规划只要设置一个保存最大值的一维数组f[N]，如果f[i]>0，那么f[i+1]=f[i]+A[i]，否则f[i+1]=A[i]，现在变成了乘法，显然不能直接套用加法的思路，因为f[i+1]不能直接从f[i]和A[i+1]推导出来，还需要看A[0-i]。

最暴力的解法很简单，就是把所有子序列A[i]*...A[j]迭代算出来，然后找到最大的，不过提交之后呵呵，很自然的内存爆了。。。

最后AC的思路又是参考了别人的博客。。。在动态规划迭代维护一个局部最大的同时，再维护一个局部最小，这样如果下一个元素遇到负数时，就可能与这个最小相乘得到当前最大的乘积和，然后每次迭代过程再维护一个全局最大值。

C++代码如下，其中maxProduct为AC的代码，maxProduct1为暴力算法：

#include <iostream>
#include <vector>
#include <stdlib.h>
#include <time.h>

using namespace std;

class Solution {
public:
    long min(long x1, long x2) {
        return x1<x2?x1:x2;
    }

    long max(long x1, long x2) {
        return x1>x2?x1:x2;
    }

    /* fast solution! */
    long maxProduct(long A[], long n) {
        if(n==1) return A[0];
        long min_local = A[0], max_local = A[0], max_global = A[0];

        for (long i = 1; i < n; ++i) {
            long max_local_old = max_local;
            max_local = max(A[i], max(A[i]*min_local, A[i]*max_local_old));
            min_local = min(A[i], min(A[i]*min_local, A[i]*max_local_old));
            max_global = max(max_local, max_global);
        }

        return max_global;
    }
    /* Memory Limit Exceeded */
    long maxProduct1(long A[], long n) {
        if(n==1) return A[0];

        long **f = new long *[n];
        for(long i=0; i<n; ++i) {
            f[i] = new long[n];
            f[i][i] = A[i];
        }
        long max = A[0];
        for(long i=1; i<n; ++i) {
            for(long j=0; j<n-i; ++j) {
                f[j][j+i] = f[j][j+i-1]*A[j+i];
                if(f[j][j+i]>max)
                    max = f[j][j+i];
            }
        }
        for(long i=0; i<n; ++i)
            delete [] f[i];
        delete [] f;
        return max;
    }
};

#define MAX_NUM 10
int main(int argc, char *argv[])
{
    srand((unsigned)time(NULL));
    long n = 100;
    Solution s;
    long *A = new long[n];
    for(long i=0; i<n; ++i) {
        A[i] = (rand()%MAX_NUM)-(rand()%MAX_NUM);
    }
    clock_t t1 = clock();
    long p1 = s.maxProduct(A, n);
    clock_t t2 = clock();
    long p2 = s.maxProduct1(A, n);
    clock_t t3 = clock();

    cout << "algorithm 1 finished in " << 1.0*(t2-t1)/CLOCKS_PER_SEC << " seconds, result: " << p1 << endl;
    cout << "algorithm 2 finished in " << 1.0*(t3-t2)/CLOCKS_PER_SEC << " seconds, result: " << p2 << endl;

    delete [] A;
    return 0;
}

nicklhy