152. Maximum Product Subarray

Question

152. Maximum Product Subarray

Solution

题目大意：求数列中连续子序列的最大连乘积

思路：动态规划实现，现在动态规划理解的还不透，照着公式往上套的，这个问题要注意正负，需要维护两个结果

Java实现：

public int maxProduct(int[] nums) {
    if (nums.length == 1) return nums[0];

    // 定义问题：状态及对状态的定义
    // 设max[i]表示数列中第i项结尾的连续子序列的最大连乘积
    // 求max[0]...max[n]中的最大值
    // 状态转移方程
    // max[0] = nums[0]
    // max[i] = Max.max(max[i-1] * nums[i], nums[i])
    int[] max = new int[nums.length];
    int[] min = new int[nums.length];
    for (int i = 0; i < nums.length; i++) {
        max[i] = min[i] = nums[i];
    }

    int product = nums[0];
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] < 0) {
            max[i] = Math.max(min[i - 1] * nums[i], max[i]);
            min[i] = Math.min(max[i - 1] * nums[i], min[i]);
            product = Math.max(max[i], product);
        } else {
            max[i] = Math.max(max[i - 1] * nums[i], max[i]);
            min[i] = Math.min(min[i - 1] * nums[i], min[i]);
            product = Math.max(max[i], product);
        }
    }
    return product;
}

别人的实现

int maxProduct(int A[], int n) {
    // store the result that is the max we have found so far
    int r = A[0];

    // imax/imin stores the max/min product of
    // subarray that ends with the current number A[i]
    for (int i = 1, imax = r, imin = r; i < n; i++) {
        // multiplied by a negative makes big number smaller, small number bigger
        // so we redefine the extremums by swapping them
        if (A[i] < 0)
            swap(imax, imin);

        // max/min product for the current number is either the current number itself
        // or the max/min by the previous number times the current one
        imax = max(A[i], imax * A[i]);
        imin = min(A[i], imin * A[i]);

        // the newly computed max value is a candidate for our global result
        r = max(r, imax);
    }
    return r;
}

关于动态规划

Ref

什么是动态规划？动态规划的意义是什么 - 知乎提问