动态规划-乘积最大子数组.md

title	date	categories	tags
动态规划：乘积最大子数组	2022-07-29 09:36:44 -0700	数据结构与算法 动态规划	动态规划

注意

GitHub 的 Markdown 渲染功能不足，文章的完整渲染欢迎来我的 博客小站 查看~~

题目描述

思路与题解

;;;id1 思路 这道题很容易陷入一个死胡同，可惜，我就陷入了~

[2,-5,-2,-4,3] 这组测试数据就很那啥，如果以我们人脑来思考，我们可以在大脑里运算一遍得出最大乘机是 24，但如果要写代码的话，在从左往右遍历的过程中，又该如何判断要放弃次最大的 20，也就是 2,-5,-2，从而选择 -2,-4,3 呢，这不就只能用暴力求解吗，我就陷入了这样的死胡同

看了官方题解后，我才明白关键的点在哪里，就是要分情况讨论啊，啊啊啊，因为有负号的干扰，所以我们还要多考虑一种情况，就是当前 i 如果是一个负数的话，那我就要找 i 前面的最小值，负负得正，从而也有可能问鼎最大值，所以就要维护最大子数组值和最小子数组值，这才是本题的关键呐！ ;;;

;;;id1 我的题解

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int prev = 1, mx = nums[0], mn = 1;
        for (const int &x : nums) {
            int t = max(x, max(prev * x, mn * x));
            // 此题的关键就在于要维护一个最小的子数组乘机
            mn = min(x, min(prev * x, mn * x));
            mx = max(mx, t);
            prev = t;
        }
        return mx;
    }
};

;;;