- 难度：
中等 - 本题涉及算法：
贪心动态规划 - 思路：
贪心动态规划 - 类似题型:
题目 152. 乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字）。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
方法一 动态规划
- 解题思路:
- 如果 数组 中不包含负数，只需要维护一个最大值
- 当出现负数的时候 ，我们可以再维护一个最小值，
- 通过维护最大值最小值，可以保证当前乘积下，最大与最小值
- 算法流程：
- 通过动态规划，记录每次乘积下的最大值和最小值，并在当前遍历结束前判断__最大值__
- 复杂度分析：
- 时间复杂度 $O(N)$ ，$N$ 为数组的长度
- 空间复杂度 $O(N)$， 我们使用了两个长度为 $N$ 数组，记录最大值和最小值
python
class Solution(object):
def maxProduct(self, nums):
le = len(nums)
if nums is None:
return 0
if le == 1:
return nums[0]
res = nums[0]
dp_max ,dp_min = [0] * le ,[0] * le
dp_max[0] = nums[0]
dp_min[0] = nums[0]
for i in range(1,le):
if nums[i] >= 0:
dp_max[i] = max(dp_max[i-1] * nums[i],nums[i])
dp_min[i] = min(dp_min[i-1] * nums[i],nums[i])
else:
dp_max[i] = max(dp_min[i-1] * nums[i],nums[i])
dp_min[i] = min(dp_max[i-1] * nums[i],nums[i])
res = max(dp_max[i],res)
return res
java
class Solution {
public int maxProduct(int[] nums) {
int len = nums.length;
int[] dp_max = new int[len];
int[] dp_min = new int[len];
int ans = nums[0];
dp_max[0] = nums[0];
dp_min[0] = nums[0];
for(int i=1;i<len;i++) {
if (nums[i] >=0) {
dp_max[i] = Math.max(dp_max[i-1] * nums[i],nums[i]);
dp_min[i] = Math.min(dp_min[i-1] * nums[i],nums[i]);
}else {
dp_max[i] = Math.max(dp_min[i-1] * nums[i],nums[i]);
dp_min[i] = Math.min(dp_max[i-1] * nums[i],nums[i]);
}
ans = Math.max(dp_max[i],ans);
}
return ans;
}
}
贪心算法
- 简化思路：
- 我们只需要记录每次遍历的最大值最小值，并替换原来的最大值和最小值
- 复杂度分析：
- 时间复杂度 $O(N)$ ，$N$ 为数组的长度
- 空间复杂度 $O(1)$， 我们使用了两个长度为 $N$ 数组，记录最大值和最小值
python
class Solution:
def maxProduct(self, nums: List[int]) -> int:
imax ,imin= 1,1
ans = nums[0]
for num in nums:
if num < 0:
imax ,imin = imin, imax
imax = max(imax * num,num)
imin = min(imin * num,num)
ans = max(imax,ans)
return ans
java
class Solution {
public int maxProduct(int[] nums) {
int imax = 1,imin = 1 ,ans = nums[0];
for (int num:nums) {
if (num<0){
int temp = imax;
imax = imin;
imin = temp;
}
imax = Math.max(imax * num,num);
imin = Math.min(imin * num,num);
ans = Math.max(imax,ans);
}
return ans;
}
}
- 如果你觉得本文对你有帮助，请点赞👍支持
- 如果有疑惑或者表达不到位的额地方 ，请在下面👇评论区指出
PREVIOUS169. 多数元素
NEXT136. 只出现一次的数字