给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积
https://leetcode-cn.com/problems/maximum-product-subarray/
示例1：
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例2：
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
Java解法
思路：
好像只需要一趟遍历即可，也不需要动态规划什么的，搞错了还把服务器搞崩了image- 还是要注意条件，子数组的长度是1到len的长度，在这里踩了个坑
- 参考官方解使用动态规划处理
- 当前位置为负数时，最大值为与前面最小值之积，最小值为与前面最大值之积，正数则相反
- 长度为1，当前位置最大最小均为 第0 个
- 长度为2，当前位置最大为
- 长度为3，最大数连续正/负数为偶数，积
- 长度为N，与F（N-1）交互得出当前位置的最大最小值
- 遍历最大值集得出最大值
- 思考中的问题
- 无法决定当前位置的最大值，其实细化下来，都是考虑包含当前位置时的最大值，最小值，而我一直考虑当前位置的最大值，这样导致前后没有逻辑链条而出错
- 还是思考太少了
package sj.shimmer.algorithm.m4_2021;
/**
* Created by SJ on 2021/4/13.
*/
class D76 {
public static void main(String[] args) {
// System.out.println(maxProduct(new int[]{2,3,-2,4}));
// System.out.println(maxProduct(new int[]{-2,0,-1}));
System.out.println(maxProduct(new int[]{1,2,-1,-2,2,1,-2,1,4,-5,4}));
}
public static int maxProduct(int[] nums) {
if (nums == null||nums.length==0) {
return 0;
}
int length = nums.length;
if (length ==1) {
return nums[0];
}
int[] max = new int[length];
int[] min = new int[length];
System.arraycopy(nums, 0, max, 0, length);//当前位置的值作为默认值
System.arraycopy(nums, 0, min, 0, length);//当前位置的值作为默认值
for (int i = 1; i < length; ++i) {
//当前位置为负数时，最大值可能为与前面最小值之积
max[i] = Math.max(nums[i] * max[i - 1], Math.max(nums[i], nums[i] * min[i - 1]));
//当前位置为负数时，最小值可能为与前面最大值之积
min[i] = Math.min(nums[i] * min[i - 1], Math.min(nums[i], nums[i] * max[i - 1]));
}
int result = max[0];
for (int i : max) {
result = Math.max(result, i);
}
return result;
}
}
image
官方解
-
动态规划
参上
- 时间复杂度： O(n)
- 空间复杂度： O(n)
-
滚动数组优化
计算时不需要存储许多之前的最大最小值，再更新时重复利用已存储的空间即可
优化空间复杂度： O(1)
