桂林网站制作报价,旅游网站策划,如何做网站的伪静态页面,苏州seo快速优化题目#xff1a;
给你一个整数数组 nums #xff0c;请你找出数组中乘积最大的非空连续子数组#xff08;该子数组中至少包含一个数字#xff09;#xff0c;并返回该子数组所对应的乘积。
思路
由于做了53. 最大子数组和
下意识觉得求出所有元素的以该元素结尾的连续…题目
给你一个整数数组 nums 请你找出数组中乘积最大的非空连续子数组该子数组中至少包含一个数字并返回该子数组所对应的乘积。
思路
由于做了53. 最大子数组和
下意识觉得求出所有元素的以该元素结尾的连续子数组的最大值然后最大值数组里求最大值。
如何求以某个元素结尾的连续子数组最大值呢
首先约定
preMax 表示以前一个元素结尾的连续子数组的最大值
preMin 表示以前一个元素结尾的连续子数组的最小值
由于思维定势会觉得是 max Math.max(元素A元素A*preMax 。
但是这样是错误的。
例如[-2,3,-2]
第一个元素最大值是 -2 第二个元素最大值是3第三个元素最大值是12。
但是根据公式第三个元素最大值 Math.max(-2*3,-2) -2.
原因就在于数组里的元素是有正负的如果只是正数那么这个方式是可以的。
所以如何求以某个元素结尾的最大值呢
如果该元素是负数max Math.max( 元素 元素*preMin
如果该元素是正数max Math.max( 元素 元素*preMax
因此对于每个元素都要记录最小值与最大值。
即
如果该元素是负数max Math.max( 元素 元素preMin min Math.min( 元素 元素preMax
如果该元素是正数max Math.max( 元素 元素preMax min Math.min( 元素 元素preMin
⇒
max Math.max(元素 元素preMin元素preMax)
min Math.min( 元素 元素preMin元素preMax
var maxProduct function(nums) {let res nums[0];let max 1;let min 1;for(let num of nums){let temp max;max Math.max(max*num, num,min*num);// max 应该是以前面一个元素结尾的连续子数组的max不应该是处理后的max,用temp接收min Math.min(min*num,num,temp*num);res Math.max(res, max);}return res;
};
