Leetcode 152. Maximum Product Subarray

Posted on | In | |

题目描述

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.

原题链接

题目要求在一个给定数组中，找到乘积最大的连续子数组。这题并不难，显然，原数组中对于乘积造成影响的显然只是元素的正负值。对于绝对值而言，除0以外，毫无疑问是单调递增的。

算法分析

尝试用动态规划来解决，利用dp[i]来表示“以nums[i]作为最后一个元素的连续乘积”。但是，显然dp[i]不能简单的由dp[i-1]给出。我们有这样一种假设：如果nums[i]<0，那么我们要使dp[i]最大，则会希望dp[i-1]是一个很小的负数；如果nums[i]>0，那么我们要使dp[i]最大，则会希望dp[i-1]是一个很大的正数。因此，可以考虑同时用两个值，一个最大值和一个最小值，来维护当前状态。

因此，现在考虑使用两个动态规划的数组max_product和min_product。对于nums[i]，进行分类讨论：

  • max_product[i-1]>0 && min_product[i-1]<0

    • nums[i]>0，则有：

      max_product[i] = nums[i]*max_product[i-1]

      min_product[i] = nums[i]*min_product[i-1])

    • nums[i]<0，则有：

      max_product[i] = nums[i]*min_product[i-1]

      min_product[i] = nums[i]*max_product[i-1]

    • nums[i]==0，则有：

      max_product[i] = nums[i]

      min_product[i] = min_product[i-1]

  • max_product[i-1]<0 && min_product[i-1]<0

    • nums[i]>0，则有：

      max_product[i] = nums[i]

      min_product[i] = nums[i]*min_product[i]

    • nums[i]<0，则有：

      max_product[i] = nums[i]*min_product[i]

      min_product[i] = min(nums[i], nums[i]*max_product[i-1])

    • nums[i]==0，则有：

      max_product[i] = nums[i]

      min_product[i] = min_product[i-1]

  • max_product[i-1]>0 && min_product[i-1]>0

    • nums[i]>0，则有：

      max_product[i] = nums[i]*max_product[i-1]

      min_product[i] = min_product[i-1]

    • nums[i]<0，则有：

      max_product[i] = max_product[i-1]

      min_product[i] = nums[i]*max_product[i-1]

    • nums[i]==0，则有：

      max_product[i] = max_product[i-1]

      min_product[i] = nums[i]

此时，还有max_product[i-1]为0或min_product[i-1]为0的情况没有考虑，但是动态规划的转换规则已经很明显了：

1
2
3
4
5
max_product[i] = max(nums[i], nums[i] * max_product[i-1]), nums[i] > 0
max_product[i] = max(nums[i], nums[i] * min_product[i-1]), nums[i] <= 0

min_product[i] = min(nums[i], nums[i] * min_product[i-1]), nums[i] > 0
min_product[i] = min(nums[i], nums[i] * max_product[i-1]), nums[i] <= 0

代码实现

由此可以得到代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int size = nums.size();
        if (size == 0) {
            return 0;
        }
        int* max_product = new int[size], *min_product = new int[size];
        max_product[0] = nums[0];
        min_product[0] = nums[0];
        int answer = nums[0];
        for (int i = 1; i < size; i++) {
            if (nums[i] > 0) {
                max_product[i] = max(nums[i], nums[i] * max_product[i-1]);
                min_product[i] = min(nums[i], nums[i] * min_product[i-1]);
            } else {
                max_product[i] = max(nums[i], nums[i] * min_product[i-1]);
                min_product[i] = min(nums[i], nums[i] * max_product[i-1]);
            }
            answer = max(answer, max_product[i]);
        }
        return answer;
    }
};

优化方案

之后在discuss区看到了一个类似的算法，并且在此之上，只利用两个值来维护当前的最大积和最小积，减小了空间复杂度。利用swap交换最大最小积，实现了我上面的较为冗长的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
}

本文为博主原创文章，转载请注明出处。