152 Maximum Product Subarray 乘积最大子序列
2024-08-30 16:04:11
找出一个序列中乘积最大的连续子序列(该序列至少包含一个数)。
例如, 给定序列 [2,3,-2,4],
其中乘积最大的子序列为 [2,3] 其乘积为 6。
详见:https://leetcode.com/problems/maximum-product-subarray/description/
Java实现:
方法一:
用两个dp数组,其中f[i]表示子数组[0, i]范围内并且一定包含nums[i]数字的最大子数组乘积,g[i]表示子数组[0, i]范围内并且一定包含nums[i]数字的最小子数组乘积,初始化时f[0]和g[0]都初始化为nums[0],其余都初始化为0。那么从数组的第二个数字开始遍历,那么此时的最大值和最小值只会在f[i-1]*nums[i]、g[i-1]*nums[i]和nums[i]这三个数字之间产生。所以我们用三者中的最大值来更新f[i],用最小值来更新g[i],然后用f[i]来更新结果res即可,由于最终的结果不一定会包括nums[n-1]这个数字,所以f[n-1]不一定是最终解,不断更新的结果res才是。
class Solution {
public int maxProduct(int[] nums) {
int n=nums.length;
int res=nums[0];
int[] f=new int[n];
int[] g=new int[n];
f[0]=nums[0];
g[0]=nums[0];
for(int i=1;i<n;++i){
f[i]=Math.max(Math.max(f[i-1]*nums[i],g[i-1]*nums[i]),nums[i]);
g[i]=Math.min(Math.min(g[i-1]*nums[i],f[i-1]*nums[i]),nums[i]);
res=Math.max(res,f[i]);
}
return res;
}
}
方法二:
class Solution {
public int maxProduct(int[] nums) {
int n=nums.length;
int res=nums[0];
int mn=nums[0];
int mx=nums[0];
for(int i=1;i<n;++i){
int tmax=mx,tmin=mn;
mx=Math.max(Math.max(tmax*nums[i],tmin*nums[i]),nums[i]);
mn=Math.min(Math.min(tmax*nums[i],tmin*nums[i]),nums[i]);
res=Math.max(res,mx);
}
return res;
}
}
参考:https://www.cnblogs.com/grandyang/p/4028713.html
最新文章
- [转载]windows 7 IIS 7.5 ASP.Net 文件上传大小限制
- <; meta >; 元素
- SQL 中With as 的用法
- [ JS 进阶 ] 如何改进代码性能 (3)
- SQL Standard Based Hive Authorization(基于SQL标准的Hive授权)
- EF查询
- 【转】 教你如何创建类似QQ的android弹出菜单
- js for循环 等腰三角形demo
- Sublime常用插件
- Scrapy爬虫框架解析
- MATLAB绘制函数图
- Spring xml配置
- Android播放功能的实现
- EAS开发报错 :数据库表 或 视图 不存在
- 【BZOJ1049】 [HAOI2006]数字序列
- 用户组修改工具samusrgrp
- Eclipse 汉化方法
- pip批量更新安装的包
- 2018.09.27 bzoj4300: 绝世好题(二进制dp)
- Python写一个根据日期计算是星期几的模块