【Leetcode】152. Maximum Product Subarray

Description

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.

Solution

public int maxProduct(int[] nums) {
        int len = nums.length;
        if (len == 1) {
            return nums[0];
        }
        int max = Integer.MIN_VALUE;
        for (int interval = 1; interval <= len; interval++) {
            for (int i = 0; i< len - interval + 1; i++) {
                int temp = 1;
                for (int j = i; j < i + interval; j++) {
                    temp *= nums[j];
                }
                max = temp > max ? temp : max;
            }
        }
        return max;
    }

Result

TLE

Analyse

本来想暴力破解，想法就是设置interval进行数组的截取，这样就会产生三重循环，时间复杂度是O(n ^ 3)，这样出现TLE也不足为奇了。

Optimization

First

public int maxProduct(int[] nums) {
        int max = nums[0];
        int min = nums[0];
        int result = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int temp = max;
            max = Math.max(Math.max(max * nums[i], min * nums[i]), nums[i]);
            min = Math.min(Math.min(temp * nums[i], min * nums[i]), nums[i]);
            result = max > result ? max : result;
        }
        return result;
    }

Second

public int maxProduct(int[] nums) {
        int max = nums[0];
        int min = nums[0];
        int result = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < 0) {
                max = max ^ min;
                min = min ^ max;
                max = max ^ min;
            }
            max = Math.max(max * nums[i], nums[i]);
            min = Math.min(min * nums[i], nums[i]);
            result = Math.max(result, max);
        }
        return result;
    }

Analyse

这里的问题是开始总以为需要卡住间隔，判断每种间隔之间的差距，就忽略了一个很重要的思想，就是要确定两个知识点：

在运算过程中max和min要同时统计，因为如果下一个值是小于零的话，那么相乘了之后max就是min，min就是max，两个值需要互换了，接下来通过nums[i]和nums[i]与其相乘的值来进行判断更大的值。

开始的思维误区是判断每个间隔里的最大值，但是其实可以就一遍for循环，循环过来之后，每一轮直接判断三个值，就可以得出每一轮的最小值和最大值，一直到最后就得到最大值。

需要注意的是，一定要同时更新最大值和最小值，因为最小值乘以负数的话就会马上变成最大值，这里需要格外注意。