hello,大家好,今天,我们来一起学习动态规划中的一种问题,这种问题是关于在一个数组中,子数组最大的乘积问题,接下来,我们正式开始!!!!!
题目很简单,意思很浅显易懂。我们来分析一下示例一:因为数组中有一个负数,所以负数一定不会选,所以2*3=6>4;最大的子数组乘积为6
我们以往解决此类问题都是根据经验+题目描述!!
对此类问题,我们的经验就是:以某一个位置为结尾,来分析问题,这一次我们也不例外,依旧延续这个方法。
有人说:以往我们不是都习惯于有dp表来表示吗??别着急,听我慢慢讲为什么不用dp表
我们就假设这个数组为nums吧,以上图我们可以把子数组分为两类,第一类:子数组长度为1,nums[i],第二类:子数组长度大于1,nums[i]*f[i-1]。这样对吗???是不对的!!!!
1.如果nums[i]>0,我们再求得以i-1结尾的最大值,就获得了以i结尾的最大值。
2.如果nums[i]<0,我们如果再求得以i-1结尾的最大值,那么,这个最大值与nums[i]相乘,这个值不就越来越小吗???,到头来,我们求到了一个最小值。
所以,为了解决这种情况,除了定义一个f[i],还要定义一个数组:
当nums[i]<0时,应该获得以i-1结尾的子数组的最小值;当nums[i]>0,应该获得以i-1为结尾的子数组的最大值,这样做还要进行一次分类讨,太麻烦,干脆我们这样做
初始化的方案有两种,这里,我们总结一下:
什么位置最容易产生越界,就是在i=0时,i-1=-1,会产生越界。
在循环之前,我们先对f[0],g[0]进行初始化,然后从i=1进行for循环初始化。f[0]=g[0]=nums[0]
把数组大小设为nums.size()+1;在下标为0的元素设置成1,为什么要这样做呢???
正好可以与 第一种方法相对应,但这种方法要注意下标,而且填入的值,不能影响后边的初始化
两个表从左往右,同时填
返回f表中的最大值