LeetCode热题100—— 152. 乘积最大子数组

https://leetcode.cn/problems/maximum-product-subarray/description/?envType=study-plan-v2&envId=top-100-liked

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

示例 1:

输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:

输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

提示:

1 <= nums.length <= 2 * 104
-10 <= nums[i] <= 10
nums 的任何子数组的乘积都 保证 是一个 32-位 整数

题解

1. 初始值 maxAns = minAns = nums[0] = 5
2. 第一轮 i=1 直接从第二个元素开始遍历即可
   1. maxAns = max(maxAns * nums[1],nums[1],minAns * nums[1]) = max(30,6,30) = 30
   2. minAns = min(maxAns * nums[1],nums[1],minAns * nums[1]) = min(30,6,30) = 6
3. 第二轮 i=2
   1. maxAns = max(maxAns * nums[2],nums[2],minAns * nums[2]) = max(-90,-3,-18) = -3
   2. minAns = min(maxAns *nums[2],nums[2],minAns * nums[2]) = min(-90,-3,-18) = -90
4. 第三轮 i=3
   1. maxAns = max(maxAns * nums[3],nums[3],minAns * nums[3]) = max(-12，4 , -360) = 4
   2. minAns = min(maxAns * nums[3],nums[3],minAns * nums[3]) = min(-12，4 , -360) = -360
5. 第四轮 i=4
   1. maxAns = max(maxAns * nums[4],nums[4],minAns * nums[4]) = max(-12，-3 , 1080) = 1080
   2. minAns = min(maxAns * nums[4],nums[4],minAns * nums[4]) = min(-12，-3 , 1080) = -12

核心思想:
负负得正，正正得正
负的越多，正的越大 (-100 * -1 > -50 * -1)

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