leetcode152.Maximum Product Subarray

发表于 更新于 分类于 ，

题目要求

1
2
3
4
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.

从一个整数数组中找到一个子数组，该子数组中的所有元素的乘积最大。
比如数组[2,-3,-2,4]的最大乘积子数组为[2,3]

思路与代码

这题目考察了动态编程的思想。从一个更高的视角看这个问题，我们可以推理一下，假如我们知道了以第i位为结尾的子数组的最大乘积值和最小乘积值，我们能否知道第(i+1)位的最大乘积值和最小乘积值呢？答案是肯定的。因为只需要比较max( nums[i+1], maxProduct[i]*nums[i+1], minProduct[i]*nums[i+1])就可以了。
至于为什么还要比较minProduct[i]*nums[i+1]，是因为如果nums[i+1]是一个负数的，那么之前的最小乘积在这里可能就成为了最大的乘积了。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int maxProduct(int[] nums) {
    //记录在遍历过程中所得到的最大乘积值
    int max = nums[0];
    for(int i = 1, curMax = max, curMin = max ; i<nums.length ; i++){
        //如果当前的值为负数，则交换curMax和curMin
        if(nums[i] < 0){
            int temp = curMax;
            curMax = curMin;
            curMin = temp;
        }
        curMax = Math.max(nums[i], curMax * nums[i]);
        curMin = Math.min(nums[i], curMin * nums[i]);
        
        //将已知最大值和当前最大值进行比较
        max = Math.max(curMax, max);
    }
    return max;
}