152. 乘积最大子数组

阳光穿透心脏的1/2处 2023-03-01 13:45 23阅读 0赞

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1amlhbjIzMw_size_16_color_FFFFFF_t_70]  
[leetcode][]

动态规划：  
dp\[i\]表示以i结尾的连续子数组的最大乘积，  
最后返回dp\[0\]到dp\[n-1\]中最大的值

class Solution {
        
    public:
        int maxProduct(vector<int>& nums) {
        
            vector<int> maxf(nums), minf(nums);
    
            for(int i = 1; i < nums.size(); i++){
        
                maxf[i] = max(maxf[i-1] * nums[i], max(minf[i-1] * nums[i], nums[i]));//正
                minf[i] = min(maxf[i-1] * nums[i], min(minf[i-1] * nums[i], nums[i]));//负
            }
    
            return *max_element(maxf.begin(), maxf.end());
        }
    };

可滚动数组优化：

class Solution {
        
    public:
        int maxProduct(vector<int>& nums) {
        
            int maxf = nums[0];
            int minf = nums[0];
    
            int res = nums[0];
            for(int i = 1; i < nums.size(); i++){
        
                int maxF = maxf, minF = minf;
                maxf = max(maxF * nums[i], max(minF * nums[i], nums[i]));
                minf = min(maxF * nums[i], min(minF * nums[i], nums[i]));
                res = max(res, maxf);
            }
    
            return res;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1amlhbjIzMw_size_16_color_FFFFFF_t_70]: /images/20230208/30f7e81641704a079b93c7f7de23eb74.png
[leetcode]: https://leetcode-cn.com/problems/maximum-product-subarray/