152. Maximum Product Subarray

Posted on | In
Words count in article: 262 | Reading time ≈ 1

题目

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

示例1:

1
2
3
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

示例2：

1
2
3
Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

解法

解法一：

动态规划

从题目意思来看，它需要求出，连续的子序列的积。那么，假设d[i]为数组第i个数字时的最大乘积。那么它的最大值就是当前值（前一个值为0或者前一个值为负，当前值为正）或者它前一个最大值乘以当前值（前一个值和当前值都为正数）或者它前一个最小值乘以当前值（前一个值为负，当前值为负）

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
public int maxProduct(int[] nums) {
        int result = nums[0];
        int min = nums[0];
        int max = nums[0];
        for (int i = 1;i < nums.length;i++) {
        	int m1 = min;
        	int m2 = max;
        	min = Math.min(m1 * nums[i], Math.min(m2 * nums[i], nums[i]));
        	max = Math.max(m1 * nums[i], Math.max(m2 * nums[i], nums[i]));
        	result = Math.max(result, max);
        }
        return result;
    }
0%