题目描述:
给你一个整数数组 nums ,请你找出数组中乘积最大的连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。
解析:
1.可以理解为寻找连续子数组,使数组乘机最大,需要考虑负数
2.新创建一个数组,每次去比较nums[i] * maxProductMemo[i-1], nums[i] * minProductMemo[i-1],
nums[i]三个的大小,更新maxProductMemo[i]和minProductMemo[i]
3.然后去判断max和maxProductMemo[i]的大小,确定是否要开新的数组
每次比较把较大值存入变量max中,最后返回max
Java:
public int maxProduct(int[] nums) { int[] maxProductMemo = new int[nums.length]; int[] minProductMemo = new int[nums.length]; maxProductMemo[0] = nums[0]; minProductMemo[0] = nums[0]; int max = nums[0]; for(int i = 1; i < nums.length; i++) { maxProductMemo[i] = Math.max(nums[i], Math.max(nums[i] * maxProductMemo[i-1], nums[i] * minProductMemo[i-1])); minProductMemo[i] = Math.min(nums[i], Math.min(nums[i] * maxProductMemo[i-1], nums[i] * minProductMemo[i-1])); max = Math.max(max, maxProductMemo[i]); } return max; }
JavaScript:
var maxProduct = function(nums) { const maxProductMemo = []; const minProductMemo = []; maxProductMemo[0] = nums[0]; minProductMemo[0] = nums[0]; let max = nums[0]; for(let i = 1; i < nums.length; i++) { maxProductMemo[i] = Math.max(nums[i], nums[i] * maxProductMemo[i-1], nums[i] * minProductMemo[i-1]); minProductMemo[i] = Math.min(nums[i], nums[i] * maxProductMemo[i-1], nums[i] * minProductMemo[i-1]); max = Math.max(max, maxProductMemo[i]); } return max; };