今日主要总结一下动态规划的一道题目，152. 乘积最大子数组

题目：152. 乘积最大子数组

Leetcode题目地址
题目描述：
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

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

子数组 是数组的连续子序列。

示例 1:
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:
输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

提示:

1 <= nums.length <= 2 * 104
-10 <= nums[i] <= 10
nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数

本题重难点

动规五部曲如下：

1. 确定dp数组（dp table）以及下标的含义
   dp[i]：包括下标i之前的最大连续子数组的乘积为dp[i]。

2. 确定递推公式
   根据一文搞懂动态规划之53. 最大子数组和问题的经验，我们很容易推导出这样的状态转移方程：
   dp[i] = max(dp[i – 1] + nums[i], nums[i]);
   可是在这里，这样做是错误的。为什么呢？
   因为这里的定义并不满足「最优子结构」。具体地讲，如果
   a={5,6,−3,4,−3}，那么此时 对应的序列是{5,30,−3,4,−3}，按照前面的算法我们可以得到答案为 30，即前两个数的乘积，而实际上答案应该是全体数字的乘积。我们来想一想问题出在哪里呢？问题出在最后一个 −3 所对应的 的值既不是 −3，也不是 4×(−3)，而是5×6×(−3)×4×(−3)。所以我们得到了一个结论：当前位置的最优解未必是由前一个位置的最优解转移得到的。
   所以这道题我们可以根据正负性进行分类讨论。
   考虑当前位置如果是一个负数的话，那么我们希望以它前一个位置结尾的某个段的积也是个负数，这样就可以负负得正，并且我们希望这个积尽可能「负得更多」，即尽可能小。如果当前位置是一个正数的话，我们更希望以它前一个位置结尾的某个段的积也是个正数，并且希望它尽可能地大。于是这里我们可以再维护一个$fmin[i]$它表示以第 i 个元素结尾的乘积最小子数组的乘积，那么我们可以得到这样的动态规划转移方程：
   
   它代表第 ii 个元素结尾的乘积最大子数组的乘积$fmax(i)$，可以考虑把加入第 i−1 个元素结尾的乘积最大或最小的子数组的乘积中，二者加上 $nums[i]$ ，三者取大，就是第 i 个元素结尾的乘积最大子数组的乘积。第 ii 个元素结尾的乘积最小子数组的乘积$fmin(i)$ 同理。

3. dp数组如何初始化
   从递推公式可以看出来dp[i]是依赖于dp[i – 1]的状态，dp[0]就是递推公式的基础。
   dp[0]应该是多少呢” />O(n)
   空间复杂度：$O(n)$

   方法二、动态规划优化解法

   C++代码

   由于第 $i$ 个状态只和第 $i-1$个状态相关，根据「滚动数组」思想，我们可以只用两个变量来维护$i-1$时刻的状态，一个维护$fmax$ ，一个维护$fmin$

   class Solution {public:    int maxProduct(vector<int>& nums) {        int dpMax = nums[0];        int dpMin = nums[0];        int res = nums[0];        for(int i = 1; i < nums.size(); i++){            int tmpMax = dpMax;            int tmpMin = dpMin;            dpMax = max(tmpMax * nums[i], max(tmpMin * nums[i], nums[i]));            dpMin = min(tmpMax * nums[i], min(tmpMin * nums[i], nums[i]));            if(dpMax > res) res = dpMax;        }        return res;    }};

   时间复杂度：$O(n)$
   空间复杂度：$O(1)$

   ---

   总结

   动态规划
   英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。
   动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的

   对于动态规划问题，可以拆解为如下五步曲，这五步都搞清楚了，才能说把动态规划真的掌握了！

   1. 确定dp数组（dp table）以及下标的含义
   2. 确定递推公式
   3. dp数组如何初始化
   4. 确定遍历顺序
   5. 举例推导dp数组

   这篇文章主要总结了分别使用动态规划和贪心算法两种方法解决了152. 乘积最大子数组问题，动态规划中依然是使用动规五部曲，做每道动态规划题目这五步都要弄清楚才能更清楚的理解题目，并且给出了优化空间复杂度的代码！
   欢迎大家关注本人公众号：编程复盘与思考随笔
   (关注后可以免费获得本人在csdn发布的资源源码)