152.Maximum-Product-SubaArray

1. Description:

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

1
2
3

For example, given the array[2,3,-2,4]`,

the contiguous subarray [2,3] has the largest product = 6.

2. Difficulty:

Medium

3. Solution:

It remains us of Maximum-Sum-SubArray, but it is more complicated

First I came up with a brute $O(n^2)$ solution.

public static int maxProduct(int[] nums) {
        int len = nums.length,max = nums[len - 1];
        if(len == 1)return nums[0];
        int[][] product = new int[len][len];
        product[len - 1][len - 1] = nums[len - 1];
        for (int i = len - 2; i >= 0; i--) {
            product[i][i] = nums[i];
            max = Math.max(max,nums[i]);
            for (int j = i + 1; j < len; j++) {
                product[i][j] = nums[i] * product[i + 1][j];
                max = Math.max(max,product[i][j]);
            }
        }
        return max;
    }

But it failed to pass OJ.

解法一：

Then I came up with another Dynamic Programming Solution.

我们知道在乘法中，只要乘数不包括0，那么结果在绝对值上也会变大，因此我们要追踪的是当前的最大以及最小值，这两者理论上都有可能在后面变成最大乘积。

参考Discuss上的一段话

Besides keeping track of the largest product, we also need to keep track of the smallest product. Why? The smallest product, which is the largest in the negative sense could become the maximum when being multiplied by a negative number.

但是我们要保证一点，就是在循环到nums[i]处时，当前步骤的最大值必须是受到nusm[i-1]影响的。在得到最大最小值时，我们要比较的是nums[i]和上一步的最大最小值的乘积以及当前nums[i].

因此在nums[i] > 0时，我们可以得到转移方程:

$max[i] = Math.max(max[i - 1] * nums[i],nums[i])$ $min[i] = Math.max(min[i-1]*nums[i],nums[i])$

在nums[i] < 0 时，我们可以得到转移方程

$max[i] = Math.max(min[i - 1] * nums[i],nums[i])$ $min[i] = Math.max(max[i-1]*nums[i],nums[i])$

在得到最后的最大值时只需遍历max数组即可。

在空间上优化：用变量max，min代替数组，每步都获得当前的最大值。

$cur\\_max =Math.max(cur\\_max,max)$

public static int maxProduct_n(int[] nums) {
    int res = nums[0],max = res,min = res,len = nums.length;
    if(len == 0) return 0;
    for(int i = 1; i < len; i++){
        if(nums[i] > 0){
            max = Math.max(nums[i] * max, nums[i]);
            min = Math.min(nums[i] * min, nums[i]);
        }
        else {
            int temp = max;
            max = Math.max(min * nums[i],nums[i]);
            min = Math.min(temp * nums[i],nums[i]);
        }
        res = Math.max(res,max);
    }
    return res;
}

解法二:

解法一代码简化。

从上一步我们可以看出，max和min的值是交换的。即在nums <= 0的时候，max和min就会发生互换。因此我们可以加入一个判断

1
2
3

if(nums[i] =< 0) swap(max,min);
 max = Math.max(nums[i] * max, nums[i]);
    min = Math.min(nums[i] * min, nums[i]);

解法三:

由于是乘法，考虑没有0的情况，每加入一个新的数，乘积的绝对值都会变大，如果整个数组有n个负数

若n为偶，则subarray就是全部array。

若n为奇，则可以得到负数为偶数个的subarray来比较乘积

头尾是正，如[2,3,-4,1,2] 就是[2,3] 和 [1,2]的比较。

头尾是负，[-4,1,-2,3,-4]就是[-4,1,-2,3],[1,-2,3,-4]。

头是正[1,-1,-3,3,-2]就是[1,-1,-3,3]

尾是正[-1,-1,-3,3,2]就是[-1,-3,3,2]

由此其实可以直观感觉出，如果有最大值的话，那么最大值一定是会包括头或者尾的。

故可以遍历两边，从头遍历一遍，从尾遍历一遍

public static int maxProduct_n(int[] nums) {
    int res = nums[0],len = nums.length,product = 1;
    if(len == 0) return 0;
    for(int i = 0; i < len; i++){
      	product *= nums[i];
        res = Math.max(res,product);
      	if(nums[i] == 0)product = 1;
    }
  	product = 1;
    for(int i = len - 1; i >= 0; i--){
      	product *= nums[i];
        res = Math.max(res,product);
      	if(nums[i] == 0)product = 1;
    }
    
    return res;
}

你好

Maximum Product subarray

152.Maximum-Product-SubaArray

1. Description:

2. Difficulty:

3. Solution: