本文主要是介绍Leetcode 152. 乘积最大子数组（Medium），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续
子数组
（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
示例 1:
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: nums = [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
提示:
1 <= nums.length <= 2 * 104-10 <= nums[i] <= 10nums的任何子数组的乘积都 保证 是一个 32-位 整数
思路：根据给的提示，是整数而且范围没有超int，所以只需要考虑负数和0的特殊情况，且数据类型只有int，所以只需要在遍历时当遇到负数或者0时，记录一下（当时的坐标+1），因为只有<=0，才会让数值有异常。然后分别把坐标0和不是最后一个结点的非正数的情况放到list里作为每次遍历的起始节点，然后取每次遍历的最大值。模拟一下，假如nums = [2,3,-2,4]，先把坐标0的放进去，list=[0]，然后向下走，走到-2时候<=0，且不是最后一个节点，放进去，list=[0, 3]，（注意：放进去的节点是以后要遍历的所以是异常节点的后一位）。最后开始遍历一个遍历的max是6，第二次是4，所以最终的max是6，具体实现：
class Solution {public int maxProduct(int[] nums) {// 当前数值int cur = 1;// 最大值int max = Integer.MIN_VALUE;// 回退坐标值List<Integer> backIndexs = new ArrayList<>();for (int i = 0; i < nums.length; i++) {if (i == 0) backIndexs.add(0);if (nums[i] <= 0 && i != nums.length-1) {// 说明是负数或0，就记录一下backIndexs.add(i+1);}}while(!backIndexs.isEmpty()) {for (int i = backIndexs.remove(0); i < nums.length; i++) {cur *= nums[i];if(cur > max) max = cur;}cur = 1;}return max;}
}还有一种思路，实际上大同小异，只是第一种，使用了集合，会导致性能的下降。第二种办法使用一次遍历，维护了三个属性值，局部最大值，局部最小值，最大值，当为结点负数的时候，局部最大值和局部最小值交换，局部最小值，就是去维护了负数的最大值，局部最大值就是维护的正数的最大值，当下一个负数出现时，min就需要和max换顺序，-max 必然小于等于 -min，max必然大于等于min
class Solution { // 该方法用于找到给定整数数组中连续子数组的最大乘积 public int maxProduct(int[] nums) { // 如果数组为空或长度为0，则没有乘积可以计算，直接返回0 if (nums == null || nums.length == 0) return 0; // maxSoFar 用于记录到目前为止找到的最大乘积 int maxSoFar = nums[0]; // maxEndingHere 用于记录以当前元素结尾的连续子数组的最大乘积 int maxEndingHere = nums[0]; // minEndingHere 用于记录以当前元素结尾的连续子数组的最小乘积（考虑到负数乘以负数可能变成最大乘积） int minEndingHere = nums[0]; // 遍历数组中的每个元素（从第二个元素开始，因为第一个元素已经在初始化时考虑过） for (int i = 1; i < nums.length; i++) { // 如果当前元素是负数，则交换 maxEndingHere 和 minEndingHere // 这是因为负数乘以当前的最大值可能变成最小值，而乘以当前的最小值（实际上是绝对值最大的负数）可能变成最大值 if (nums[i] < 0) { int temp = maxEndingHere; maxEndingHere = minEndingHere; minEndingHere = temp; } // 更新以当前元素结尾的连续子数组的最大乘积 // 如果当前元素本身就比之前的最大乘积还大，或者之前的最大乘积乘以当前元素更大，则更新 maxEndingHere maxEndingHere = Math.max(nums[i], maxEndingHere * nums[i]); // 更新以当前元素结尾的连续子数组的最小乘积 // 如果当前元素本身就比之前的最小乘积还小，或者之前的最小乘积乘以当前元素更小（考虑负数情况），则更新 minEndingHere minEndingHere = Math.min(nums[i], minEndingHere * nums[i]); // 更新到目前为止找到的最大乘积 // 如果以当前元素结尾的最大乘积比之前记录的最大乘积还大，则更新 maxSoFar maxSoFar = Math.max(maxSoFar, maxEndingHere); } // 返回到目前为止找到的最大乘积 return maxSoFar; }
}这篇关于Leetcode 152. 乘积最大子数组（Medium）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
