152.乘积最大子数组
数组 最大 乘积
2023-09-14 09:01:28 时间
乘积最大子数组
给你一个整数数组 nums ,请你找出数组中乘积最大的连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
实例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
来源:Leetcode
链接:link
public int maxProduct(int[] nums) {
int max = Integer.MIN_VALUE, imax = 1, imin = 1;
for(int i = 0; i < nums.length; i++) {
if(nums[i] < 0) {
int tem = imax;
imax = imin;
imin = tem;
}
imax = Math.max(imax*nums[i], nums[i]);
imin = Math.min(imin*nums[i], nums[i]);
max = Math.max(max, imax);
}
return max;
}
解题思路:
标签:动态规划
遍历数组时计算当前最大值,并不断更新
令imax为当前最大值,则当前最大值为imax = max(imax * nums[i], nums[i])
由于存在负数,那么会导致最大的变最小,最小的变最大,因此还需要维护当前的最小值imin,imin = min(imin * nums[i], nums[i])
当出现负数时则imax与imin进行交换再进行下一步计算
时间复杂度:O(n)
相关文章
- 检查两个多维数组 是否一致
- Java实现最大连续乘积子数组
- Java实现最大连续乘积子数组
- Java实现最大连续子数组和
- 广义表和数组
- LeetCode:152_Maximum Product Subarray | 最大乘积连续子数组 | Medium
- 向数组中添加数组
- 数组中重复的值
- LeetCode-1798. 你能构造出连续值的最大数目【贪心,数组】
- 【基础入门题005】求列表(或数组)嵌套的最大深度
- [转]php判断一个数组是另一个数组的子集
- 华为OD机试 - 优雅子数组(Java & JS & Python)
- Python编程语言学习:仅需一行代码将字符串化的数字数组、int数组、float数组实现之间互换(将一个字符串数组转换成整型数组)
- 【JavaEE基础与高级 第6章】JavaEE中的二维数组详细介绍与应用
- (微软100题)3.求子数组的最大和
- 【华为OD机试 2023最新 】 组装新的数组(C++ 100%)
- 643. 子数组最大平均数 I-固定滑动窗口
- 152. 乘积最大子数组-动态规划
- 【数据结构】测试5 数组和广义表
- 习题 6.8 找出一个二维数组中的鞍点,即该位置上的元素在该行上最大、在该列上最小。也可能没有鞍点。
- Leetcode 643. 子数组最大平均数 I(网友思路)
- Leetcode 152. 乘积最大子数组(暴力破解居然可以通过!)
- 二维数组中的最大联通子数组
- js将form表单序列化[json字符串、数组、对象]
- 【LeetCode】152.乘积最大子数组
- python工具方法 12 随机生成特定范围值的数组