【leetcode-152】 乘积最大子序列
2024-08-30 10:56:15
给定一个整数数组 nums ,找出一个序列中乘积最大的连续子序列(该序列至少包含一个数)。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
由于存在负数,那么会导致最大的变最小的,最小的变最大的。因此还需要维护当前最小值imin
max表示以当前节点为终结节点的最大连续子序列乘积 min表示以当前节点为终结节点的最小连续子序列乘积
我们只要记录前i的最小值, 和最大值, 那么 dp[i] = max(nums[i] * pre_max, nums[i] * pre_min, nums[i])
class Solution {
public int maxProduct(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int res = nums[0];
int pre_max = nums[0];
int pre_min = nums[0];
for (int i = 1; i < nums.length; i++) {
int cur_max = Math.max(Math.max(pre_max * nums[i], pre_min * nums[i]), nums[i]);
int cur_min = Math.min(Math.min(pre_max * nums[i], pre_min * nums[i]), nums[i]);
res = Math.max(res, cur_max);
pre_max = cur_max;
pre_min = cur_min;
}
return res;
}
}
我:
public int maxProduct(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int max = nums[0];
int pre_max = nums[0];
int pre_min = nums[0];
for (int i=1;i<nums.length;i++) {
int cur_max = Math.max(Math.max(pre_max*nums[i],pre_min*nums[i]),nums[i]);
int cur_min = Math.min(Math.min(pre_max*nums[i],pre_min*nums[i]),nums[i]);
max = Math.max(max,cur_max);
pre_max = cur_max;
pre_min = cur_min;
}
return max;
}
最新文章
- laravel框架中容器类简化代码-摘自某书
- Oracle Linux
- Spark Streaming源码解读之Job动态生成和深度思考
- Orchard Platform v1.7.2 发布
- <;转>;RowState 介绍
- 传统的Ado.net 参数设置:params SqlParameter[] commandParameters
- javaweb学习总结一(eclipse常用快捷键、debug调试以及junit测试框架)
- bzoj 2004: [Hnoi2010]Bus 公交线路
- ESP8266最小系统
- 采用VSPD、ModbusTool模拟串口、MODBUS TCP设备进行Python采集软件开发
- Python中使用多进程来实现并行处理的方法小结
- java实现自动生成小学四则运算——朱庭震,詹祺豪
- Java,JDK动态代理的原理分析
- linux挂载SD卡
- 调用webservices报错 原因是没有导入commons-logging和commons-discovery
- cef开启摄像头和录音
- shell 中>;/dev/null 2>;&;1含义
- Android -- 自定义标题栏,背景颜色填充满
- 【LeetCode】【Python题解】Reverse Integer
- Thinkphp 修改U方法按路由规则生成url