一 问题说明
乘积最大子数组
Detailed Description
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），要求返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
提示：
1 <= nums.length <= 2 * 104
-10 <= nums[i] <= 10
nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数
i | nums[i] | max_dp (以i结尾的最大积) | min_dp (以i结尾的最小积) | 全局最大积 (res) |
0 | 2 | 2(从2开始) | 2(从2开始) | 2 |
1 | 3 | 6(2*3) | 3(从3开始) | 6 |
2 | -2 | -2(从-2开始) | -12(6*-2) | 6 |
3 | 4 | 4(从4开始) | -48(-12*4) | 6 |
二 C++代码实现+注释
#include <vector>#include <memory>#include <stdio.h>intmaxMulti(conststd::vector<int>&arr){intmax_dp;intmin_dp;intresult=arr[0];max_dp=min_dp=arr[0];for(inti=1;i<arr.size();i++){inttemp=arr[1];//因为存在正负关系，所以，记录最小值，也就是负最大值inttemp_max=max_dp;//关键的状态转移max_dp=std::max(std::max(temp,max_dp*temp),min_dp*temp);min_dp=std::min(std::min(temp,max_dp*temp),min_dp*temp);//更新最大值result=std::max(result,max_dp);}returnresult;}intmain(){std::vector<int>arr={2,3,8,-3,4,-5,9};intresult=maxMulti(arr);printf("result ######## %d\n",result);}代码为何不像动态规划一样，找中间的一段子集？因为这里数据乘得越多，绝对值越大，所以从开头开始乘即可。
三 编译运行
g++ -g -o maxMulti maxMulti.cc
./maxMulti
result ######## 1458
