dedecms 网站名称装修网名大全
张小明 2026/1/10 10:27:17
dedecms 网站名称,装修网名大全,wordpress添加自定义按钮,做网站需要字体切换一 问题说明乘积最大子数组Detailed Description给你一个整数数组 nums #xff0c;请你找出数组中乘积最大的非空连续子数组#xff08;该子数组中至少包含一个数字#xff09;#xff0c;要求返回该子数组所对应的乘积。测试用例的答案是一个 32-位 整数。提示#xff1…一 问题说明乘积最大子数组Detailed Description给你一个整数数组 nums 请你找出数组中乘积最大的非空连续子数组该子数组中至少包含一个数字要求返回该子数组所对应的乘积。测试用例的答案是一个 32-位 整数。提示1 nums.length 2 * 104-10 nums[i] 10nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数inums[i]max_dp (以i结尾的最大积)min_dp (以i结尾的最小积)全局最大积 (res)022(从2开始)2(从2开始)2136(2*3)3(从3开始)62-2-2(从-2开始)-12(6*-2)6344(从4开始)-48(-12*4)6二 C代码实现注释#include vector#include memory#include stdio.hintmaxMulti(conststd::vectorintarr){intmax_dp;intmin_dp;intresultarr[0];max_dpmin_dparr[0];for(inti1;iarr.size();i){inttemparr[1];//因为存在正负关系所以记录最小值也就是负最大值inttemp_maxmax_dp;//关键的状态转移max_dpstd::max(std::max(temp,max_dp*temp),min_dp*temp);min_dpstd::min(std::min(temp,max_dp*temp),min_dp*temp);//更新最大值resultstd::max(result,max_dp);}returnresult;}intmain(){std::vectorintarr{2,3,8,-3,4,-5,9};intresultmaxMulti(arr);printf(result ######## %d\n,result);}代码为何不像动态规划一样找中间的一段子集因为这里数据乘得越多绝对值越大所以从开头开始乘即可。三 编译运行g -g -o maxMulti maxMulti.cc./maxMultiresult ######## 1458