LeetCode热题100--152. 乘积最大子数组--中等

题目

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

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

请注意，一个只包含一个元素的数组的乘积是这个元素的值。

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

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

题解

classSolution{publicintmaxProduct(int[]nums){intmax=Integer.MIN_VALUE,imax=1,imin=1;for(inti=0;i<nums.length;i++){if(nums[i]<0){inttmp=imax;imax=imin;imin=tmp;}imax=Math.max(imax*nums[i],nums[i]);imin=Math.min(imin*nums[i],nums[i]);max=Math.max(max,imax);}returnmax;}}

解析

出自：画解算法：152. 乘积最大子序列

classSolution{publicintmaxProduct(int[]nums){// 初始化全局最大乘积为最小整数值（用于后续更新）intmax=Integer.MIN_VALUE;// imax：以当前元素结尾的子数组的最大乘积// imin：以当前元素结尾的子数组的最小乘积（用于处理负数）intimax=1,imin=1;// 遍历数组中的每一个元素for(inti=0;i<nums.length;i++){// 如果当前数字是负数，交换 imax 和 imin// 原因：负数会使最大值变最小，最小值变最大if(nums[i]<0){inttmp=imax;imax=imin;imin=tmp;}// 更新以当前元素结尾的最大乘积：// 要么延续之前的子数组（imax * nums[i]），要么从当前元素重新开始（nums[i]）imax=Math.max(imax*nums[i],nums[i]);// 更新以当前元素结尾的最小乘积（同样考虑重新开始 or 延续）imin=Math.min(imin*nums[i],nums[i]);// 更新全局最大乘积（记录历史最大值）max=Math.max(max,imax);}// 返回整个数组中子数组的最大乘积returnmax;}}