leetcode152乘积最大子数组

太过爱你忘了你带给我的痛 2022-12-19 06:25 76阅读 0赞

题目:

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

示例 1:

输入: \[2,3,-2,4\]  
输出: 6  
解释: 子数组 \[2,3\] 有最大乘积 6。  
示例 2:

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

解法:该题目开始想用滑动窗口去解决奈何找不全滑动条件 就开始尝试使用动态规划

与之前动态规划不同的是 最优子结构存在两个max 和 min 即上一步找到的最小子结构乘上这一步也可能是最大子结构

如果当前数值为负数 那么让前面的数尽可能负的大 反之正的大

代码如下:

class Solution {
    public:
        int maxProduct(vector<int>& nums) {
            //考虑使用动态规划解决此题目 一般而言求最大最小 最多最少都可以用动态规划
            int res=nums[0];
            int max1=nums[0];
            int min1=nums[0];
            for(int i=1;i<nums.size();i++){
                int tem=max1;
                max1=max(max1*nums[i],min1*nums[i],nums[i]);
                min1=min(tem*nums[i],min1*nums[i],nums[i]);
                //cout<<max1<<" "<<min1<<endl;
                if(res<max1) res=max1;
            }
            return res;
        }
        int max(int a,int b,int c){
            a=a>b?a:b;
            a=a>c?a:c;
            return a;
        }
        int min(int a,int b,int c){
            a=a<b?a:b;
            a=a<c?a:c;
            return a;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，76人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode-152. 乘积最大子数组

目录思路动态规划题目来源 [152. 乘积最大子数组][152.] 思路这题跟LeetCode-53. 最大子数组和很像

古城微笑少年丶/ 2024年03月24日 17:27/ 0 赞/ 5 阅读

相关 LeetCode152. 乘积最大子数组

题目难度：中等题目描述： > 给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。 ![在这里

素颜马尾好姑娘i/ 2023年01月22日 12:46/ 0 赞/ 99 阅读

相关 leetcode152乘积最大子数组

题目: 给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。示例 1: 输入: \[2,3,-2

太过爱你忘了你带给我的痛/ 2022年12月19日 06:25/ 0 赞/ 77 阅读

相关乘积最大子数组

乘积最大子数组 1、参考资料 https://leetcode-cn.com/problems/maximum-product-subarray/ 2、题目要求

柔情只为你懂/ 2022年12月08日 01:47/ 0 赞/ 182 阅读

相关 leetcode 152. Maximum Product Subarray | 152. 乘积最大子数组（Java）

题目 [https://leetcode.com/problems/maximum-product-subarray/][https_leetcode.com_probl

亦凉/ 2022年09月04日 09:51/ 0 赞/ 144 阅读

相关子数组最大乘积

给定一个double类型的数组arr，其中的元素可正可负可0，返回子数组累乘的最大乘积。例如arr=\[-2.5，4，0，3，0.5，8，-1\]，子数组\[3，0.5，8\]

不念不忘少年蓝@/ 2022年08月18日 02:15/ 0 赞/ 158 阅读

相关 LeetCode 152.Maximum Product Subarray (乘积最大子序列)

题目描述：给定一个整数数组 `nums` ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。示例 1: 输入: [2,3,-2,4] 输出

喜欢ヅ旅行/ 2022年05月08日 19:48/ 0 赞/ 167 阅读

相关 leetcode152. 乘积最大子序列(dp)

给定一个整数数组 `nums` ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。示例 1: 输入: [2,3,-2,4] 输出: 6

àì夳堔傛蜴生んèń/ 2021年09月28日 15:36/ 0 赞/ 248 阅读

相关 LeetCode : 152. Maximum Product Subarray 最大乘积子数组

试题： Given an integer array nums, find the contiguous subarray within an array (contain

绝地灬酷狼/ 2021年06月24日 16:10/ 0 赞/ 361 阅读

相关 152.乘积最大子数组

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

梦里梦外;/ 2021年06月22日 15:38/ 0 赞/ 364 阅读