[LeetCode] 152. Maximum Product Subarray

时间：2020-05-18 12:42:44 阅读：71 评论：0 收藏：0 [点我收藏+]

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

Example 1:

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

Example 2:

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

乘积最大子数组。这个题跟53题很像，53题问的是加和最大的子数组，这个题问的是乘积最大的子数组。思路依然是动态规划，这里dp[i]的含义是以num[i]结尾的子数组的最大值是多少。初始值是nums[0]，状态转移方程分如下几种情况，因为数组中会存在负数所以需要记录两个变量，一个是max一个是min，记录遍历到当前位置i的时候，局部的最大值和最小值。记录最小值的原因是有可能下一个数字又是负数的话，再乘以这个最小值，会比之前记录到的最大值还要大。

时间O(n)

空间O(1)

Java实现

 1 class Solution {
 2     public int maxProduct(int[] nums) {
 3         // corner case
 4         if (nums == null || nums.length == 0) {
 5             return 0;
 6         }
 7 
 8         // normal case
 9         int max = nums[0];
10         int min = nums[0];
11         int res = nums[0];
12         for (int i = 1; i < nums.length; i++) {
13             int temp = max;
14             max = Math.max(Math.max(max * nums[i], min * nums[i]), nums[i]);
15             min = Math.min(Math.min(temp * nums[i], min * nums[i]), nums[i]);
16             res = Math.max(res, max);
17         }
18         return res;
19     }
20 }