动态规划问题之乘积最大子数组问题

hello，大家好，今天，我们来一起学习动态规划中的一种问题，这种问题是关于在一个数组中，子数组最大的乘积问题，接下来，我们正式开始！！！！！

一.题目描述

 题目很简单，意思很浅显易懂。我们来分析一下示例一：因为数组中有一个负数，所以负数一定不会选，所以2*3=6>4;最大的子数组乘积为6

二.讲解算法原理

1.状态描述

我们以往解决此类问题都是根据经验+题目描述！！

对此类问题，我们的经验就是：以某一个位置为结尾，来分析问题，这一次我们也不例外，依旧延续这个方法。

f[i]:以i为结尾的子数组中的成绩最大值

有人说：以往我们不是都习惯于有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],还要定义一个数组：

g[i]:以i为结尾的所有子数组中的最小值

2.状态转移方程

当nums[i]<0时，应该获得以i-1结尾的子数组的最小值；当nums[i]>0，应该获得以i-1为结尾的子数组的最大值，这样做还要进行一次分类讨，太麻烦，干脆我们这样做

f[i]

g[i]

3.初始化

初始化的方案有两种，这里，我们总结一下：

什么位置最容易产生越界，就是在i=0时，i-1=-1，会产生越界。

1>:

在循环之前，我们先对f[0],g[0]进行初始化，然后从i=1进行for循环初始化。f[0]=g[0]=nums[0]

2>

把数组大小设为nums.size()+1;在下标为0的元素设置成1，为什么要这样做呢？？？

正好可以与 第一种方法相对应，但这种方法要注意下标，而且填入的值，不能影响后边的初始化

 4.填表顺序

两个表从左往右，同时填

5.返回值

返回f表中的最大值

三.代码实现