LeetCode0152.乘积最大子数组：dp+原地滚动

力扣题目链接&＃xff1a;https://leetcode.cn/problems/maximum-product-subarray/

给你一个整数数组 nums &＃xff0c;请你找出数组中乘积最大的非空连续子数组&＃xff08;该子数组中至少包含一个数字&＃xff09;&＃xff0c;并返回该子数组所对应的乘积。

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

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

示例 1:

输入: nums &＃61; [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: nums &＃61; [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

提示:

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

方法一&＃xff1a;dp &＃43; 原地滚动

需要两个变量$m$和$M$&＃xff0c;分别表示以当前处理到的数字为结尾的乘积最大子数组

初始值$m$和$M$都是数组中第一个元素nums[0]

$i$从下标1开始遍历数组&＃xff0c;既然要以下标$i$为连续数组的结尾&＃xff0c;那么就有三种选择&＃xff1a;

1. 只选择当前这个下标为$i$的元素&＃xff08;$nums[i]$&＃xff09;
2. 使用以上一个元素结尾的子数组的最大乘积 乘上 这个元素&＃xff08;$nums[i]\ast M$&＃xff09;
3. 使用以上一个元素结尾的子数组的最小乘积 乘上 这个元素&＃xff08;$nums[i]\ast m$&＃xff09;

每遍历到每一个元素时&＃xff0c;计算上述三个新的可能的极值&＃xff0c;并更新$m$和$M$&＃xff0c;同时记录一下整个遍历过程中答案的最大值即可。

Q&S: 为什么还要记录最小值$m$而不是仅仅记录最大值$M$&＃xff1f;

因为最大值可能由两个负数相乘得到。如果是两个负数相乘的话&＃xff0c;负数越小乘积越大。

• 时间复杂度$O(n)$&＃xff0c;其中$n$是数组nums中元素的个数
• 空间复杂度$O(1)$

AC代码

C&＃43;&＃43;

class Solution {
public:int maxProduct(vector<int>& nums) {int ans &＃61; nums[0];int m &＃61; nums[0], M &＃61; nums[0];for (int i &＃61; 1; i < nums.size(); i&＃43;&＃43;) {int timesLastm &＃61; m * nums[i];int timesLastM &＃61; M * nums[i];m &＃61; min(nums[i], min(timesLastm, timesLastM));M &＃61; max(nums[i], max(timesLastm, timesLastM));ans &＃61; max(ans, M);}return ans;}
};


同步发文于CSDN&＃xff0c;原创不易&＃xff0c;转载请附上原文链接哦~
Tisfy&＃xff1a;https://letmefly.blog.csdn.net/article/details/126094071