[leetcode]152.乘积最大子数组

发布时间:2021-10-22 10:35:11

给你一个整数数组 nums ,请你找出数组中乘积最大的连续子数组(该子数组中至少包含一个数字)。


示例 1:


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

示例 2:


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

思路:
动态规划:
类似于最大子序列和的思想,不过本题说的是最大子数组,即中间必须要连续,而且存在负数,由于负负得正,即如果遍历到i的时候dp[i]保存当前的最大值,若nums[i]<0则dp[i]*nums[i+1]为最小值,同理,若dp[i]保存遍历到i的最小值,nums[i+1]为负,则dp[i]*nums[i+1]为最大值,所以本题需要两个dp数组,分别保存到当前的最大值与最小值
状态转移方程:


maxDP[i+1]=max(maxDP[i]*nums[i+1],nums[i+1],maxDp[i]*A[i+1])
minDP[i+1]=min(minDP[i]*nums[i+1],nums[i+1],minDp[i]*A[i+1])

初始maxDP[0]=minDP[0]=nums[0].
最后返回maxDP[nums.size()-1]即可。
优化:不使用dp数组,可以直接用两个整型变量保存当前最大值与最小值,遍历到最后输出最大值即可。


AC代码:(C++)


class Solution {
public:
int maxProduct(vector& nums) {
int size = nums.size();
if (size == 0)
return 0;
else if (size == 1)
return nums[0];
int maxP = nums[0], minP = nums[0], ans = nums[0];
for (int i = 1; i < size; i++) {
int temp = maxP;
maxP = max(max(maxP * nums[i], nums[i]), minP * nums[i]);
minP = min(min(temp * nums[i], nums[i]), minP * nums[i]);
ans = max(maxP, ans);
}
return ans;
}
};

相关文档

  • osmdroid中为何显示空地图
  • 网络创业的优点
  • 教师节给老师的祝福问候语
  • 空调制冷压缩机不工作是什么原因
  • 交通安全手抄报版
  • 精选猴年春节祝福语
  • 华为手机文件夹加密码怎么设置 华为手机文件夹加密码如何设置
  • 春节重庆周边有哪些必去的旅游景点春节可以去哪里玩
  • 菜叶变黄能炒了能吃吗
  • 将Qt与本地数据库连接起来
  • 关于汽车网络技术的论文
  • 电脑频繁卡关机怎么办
  • Cesium开发:模型实体高亮
  • 个人和企业的发展规划
  • 单亲家庭对孩子的影响有多大
  • 2021考研英语:阅读解题技巧的关键
  • 五行属木和土的女孩名字
  • 八皇后时间复杂度_2698 八皇后问题
  • 中学生制定的学习计划
  • 凡卡续写(转载)
  • 澳大利亚探亲签证有效期多长时间
  • 记一次线上异常的排查和定位
  • 挫折的意思是什么
  • 生肖属猪财运分析
  • 学校卫生温馨提示语
  • 5篇实用产品设计委托合同范本
  • 论文清单:SIGIR 2021推荐系统相关论文分类整理
  • 腾讯云Centos7搭建图形界面详解
  • 喃喃细语的成语解释
  • 乡镇三大班子届满的述职报告
  • 猜你喜欢

    电脑版