day16 乘积最大子数组

懈怠了。
不能以忙为借口。

读题

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
请注意，一个只包含一个元素的数组的乘积是这个元素的值。

思路

子数组，需要是连续的，之前做的题目很多都是放弃了顺序信息。
数组 nums 的数量很大，但是每个数据是在-10 到 10 之间，考虑继续使用哈希表记录；但是子数组需要是连续的，哈希表只能计数，不行。
首先暴力肯定能做出来，即遍历每个数字开头的子数组，记录并比较乘积大小，时间至少 O(n^2) 甚至 O(n^3) 了，空间也会很大。因为没法判断停止条件（万一后面还有更大的），会导致时间复杂度特别特别大。

---

然后想到一个子数组往前往后增加数字，都是子数组，于是尝试实现 dp。应该还是可行的，有状态和递推，状态就是“当前子数组的乘积”，递推是之后的子数组的乘积；或者如果从全局看来，状态是“当前位置之前的子数组乘积最大值”，递推是

考虑到有数字是负数，于是只保存绝对值；但是要输出的肯定还是正数，所以应该至少保存两个数字，一个正的最大值，一个负的绝对值最大值。然后每一个数组的位置都对应这两个正负最大值，也就是状态。遍历完成一遍之后，可以再遍历一边这两个最大值数组，寻找最大值（因为不要求找到对应的数组，而是只需要最大值即可）。也可以不遍历，在第一遍的时候直接就判断了。
如果要想令不是乘积最大值，那么当前位置是 0，或者是负数（转化为了负的绝对值最大值）；总之不可能是小数，绝对值一定是 0 或者大于等于 1 的。

• 初始条件：第一个数字，可以被视作单元素子数组
• 递推条件：
  • 将上一位置的 max 赋予当前位置的 max
  • 当前位置的 max 乘以当前的 num
  • 判断当前位置 max 是否大于前一个？若是，则更新全局 max；若否，则下一步

有代码：

#include <algorithm>

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        if(!nums.size()) return 0;
        vector<int> maxs(nums.size());
        vector<int> mins(nums.size());
        int max_num=nums[0];
        maxs[0]=nums[0];
        mins[0]=nums[0];
        for(int i=1;i<nums.size();i++){
            maxs[i] = max({nums[i],maxs[i-1]*nums[i],mins[i-1]*nums[i]});
            mins[i] = min({nums[i],maxs[i-1]*nums[i],mins[i-1]*nums[i]});
            max_num=max(max_num,maxs[i]);
        }
        return max_num;
    }
};

结果

0 ms，18.04 MB，空间一般，时间可以。
是因为我开了两个数组吗？

能想到 dp 纯属偶然，能寻思着解出来更是偶然。我觉得这题能这么做纯属是因为不是 0 就是 大于等于 1 的数字，不会出现小数，因此可以放心一路递推，可以直接用 max 判断大小，直接丢弃小的那个（因为如果出现了小于之前的 max，那就一定是 0 或者负数；负数的情况可以用 min 来记录，正数就可以直接丢弃）
总而言之这是针对这一道题的特例，没有办法推广到其他题目，哪怕是改变了 nums 的范围，也就不能这么做了。

官方题解

思路基本一样，但是官方题解优化了空间：
由于第 i 个状态只和第 i−1 个状态相关，根据「滚动数组」思想，我们可以只用两个变量来维护 i−1 时刻的状态。
这样就直接把数组简化成了两个数字。

感想

动态规划是块砖，哪里需要往哪搬。