网站公司建设个服务号多少钱,电子签名在线生成器,公司网站需求说明书,上海十大策划公司排名题目 给你一个整数数组 nums #xff0c;请你找出数组中乘积最大的非空连续 子数组#xff08;该子数组中至少包含一个数字#xff09;#xff0c;并返回该子数组所对应的乘积。 测试用例的答案是一个 32-位 整数。 请注意#xff0c;一个只包含一个元素的数组的乘积是这个…题目给你一个整数数组 nums 请你找出数组中乘积最大的非空连续 子数组该子数组中至少包含一个数字并返回该子数组所对应的乘积。测试用例的答案是一个 32-位 整数。请注意一个只包含一个元素的数组的乘积是这个元素的值。数据范围1 nums.length 2 * 104-10 nums[i] 10nums 的任何子数组的乘积都 保证 是一个 32-位 整数测试用例示例 1:输入:nums[2,3,-2,4]输出:6解释:子数组[2,3]有最大乘积6。示例2输入:nums[-2,0,-1]输出:0解释:结果不能为2,因为[-2,-1]不是子数组。题解1动态规划时空OnclassSolution{publicintmaxProduct(int[]nums){intnnums.length;// maxdp[i] 记录以 nums[i] 结尾的子数组的最大乘积longmaxdp[]newlong[n];// mindp[i] 记录以 nums[i] 结尾的子数组的最小乘积用来等“负负得正”longmindp[]newlong[n];// 初始化每个单独的元素自身就是一个乘积for(inti0;in;i){maxdp[i]nums[i];mindp[i]nums[i];}// 从第二个元素开始计算for(inti1;in;i){// 最大值状态转移// 前面的最大乘积 * 当前数、当前数自己单干、前面的最小乘积 * 当前数负负得正maxdp[i]Math.max(maxdp[i-1]*nums[i],Math.max(nums[i],mindp[i-1]*nums[i]));// 最小值状态转移// 前面的最小乘积 * 当前数、当前数自己单干、前面的最大乘积 * 当前数正数乘负数变成极小值mindp[i]Math.min(mindp[i-1]*nums[i],Math.min(nums[i],maxdp[i-1]*nums[i]));if(mindp[i](-131)){mindp[i]nums[i];}}// 遍历整个 maxdp 数组寻找全局最大值longmaxmaxdp[0];for(inti1;in;i){maxMath.max(max,maxdp[i]);}return(int)max;}}题解2滚动数组优化空间时间相同空间o1classSolution{publicintmaxProduct(int[]nums){// 【瘦身第一步用变量代替数组】// maxF 记录“上一个位置”算出来的最大乘积// minF 记录“上一个位置”算出来的最小乘积// 这里用 long 类型完美避开了你之前代码里 int 类型溢出导致判断失效的 BuglongmaxFnums[0],minFnums[0];// ans 用来随时记录全局的最大值初始值为数组的第一个元素intansnums[0];intlengthnums.length;// 从第二个元素索引 1开始遍历for(inti1;ilength;i){// ⚠️【瘦身核心技巧快照缓存】⚠️// 因为接下来的计算中我们会先更新 maxF。// 如果不把旧的 maxF 存起来下面计算新的 minF 时就会用到“刚刚算出的新 maxF”导致逻辑彻底错乱。// 所以必须用 mx 和 mn 把“上一轮的最终状态”先缓存下来。longmxmaxF,mnminF;// 计算当前位置的最大乘积// mx * nums[i] (前面的最大乘积 * 当前数)// mn * nums[i] (前面的最小乘积 * 当前数如果当前数是负数这里就会“负负得正”变成最大值)// nums[i] (前面不管了自己从头开始算)maxFMath.max(mx*nums[i],Math.max(nums[i],mn*nums[i]));// 计算当前位置的最小乘积// 同理取三者中的最小值用来给未来可能遇到的负数做准备minFMath.min(mn*nums[i],Math.min(nums[i],mx*nums[i]));// 【防溢出终极守卫】// 因为 minF 是 long 类型这里判断它是否小于 int 的最小值-2147483648。// 如果小于说明这个负数太小了就算以后再乘负数“负负得正”结果也会超出 int 的上限题目要求答案在 int 范围内。// 所以直接截断把它重置为当前数字。if(minF-131){minFnums[i];}// 【瘦身第二步边算边比较省去最后的 for 循环】// 每次算出当前的 maxF 后顺手和全局的 ans 比一下把更大的留下来。// 注意这里要把 maxF 强转回 int。ansMath.max((int)maxF,ans);}returnans;}}思路这道题还是有一定难度的虽然代码看起来很简单但是写动态规划的惯性思维就很难想到维护两个数组比如博主TWT。题解1的逻辑直接看我代码备注就行了进一步的思路看下图。关于题解2就是非常典型的动态规划典型的滚动数组当动态规划的状态转移方程中只与上一个动态数组值有关系时就可以使用滚动数组用一个变量将数组进行替代优化从而节约空间复杂度。