LeetCode 0152. Product Maximum Subarray: dp + Roll in Place

【LetMeFly】152.乘积最大子数组：dp + 原地滚动

力扣题目链接：https://leetcode.cn/problems/maximum-product-subarray/

给你一个整数数组 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-位 整数

方法一：dp + 原地滚动

需要两个变量$m$和$M$,Respectively, it ends with the currently processed number乘积最大子数组

初始值$m$和$M$are the first elements in the arraynums[0]

$i$从下标1开始遍历数组,Since you want to subscript$i$is the end of a contiguous array,Then there are three options：

1. Select only the current subscript as$i$的元素（$nums[i]$）
2. Use the largest product of subarrays ending with the previous element 乘上 这个元素（$nums[i]\ast M$）
3. Use the least product of subarrays ending with the previous element 乘上 这个元素（$nums[i]\ast m$）

Each time it traverses to each element,Calculate the three new possible extrema above,并更新$m$和$M$,At the same time, record the maximum value of the answer during the entire traversal process.

Q&S: Why even record the minimum value$m$instead of just recording the maximum value$M$？

Because the maximum value may be obtained by multiplying two negative numbers.If you multiply two negative numbers,The smaller the negative number, the larger the product.

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

AC代码

C++

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

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