leetcode算法-最大乘积子数组

一 问题说明

乘积最大子数组

Detailed Description

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），要求返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

提示：

1 <= nums.length <= 2 * 104

-10 <= nums[i] <= 10

nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数

二 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