leetcode热题HOT 152. 乘积最大子数组

本文主要是介绍leetcode热题HOT 152. 乘积最大子数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、问题描述：

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。

二、问题分析：

1. 考虑到乘积的特性，当乘以负数时，最大乘积会变成最小乘积，最小乘积会变成最大乘积。因此，在更新当前位置的最大乘积和最小乘积时，需要考虑前一个位置的最大乘积和最小乘积，并与当前元素相乘，以确保不会错过最大乘积或最小乘积。
2. 具体而言:当前元素 nums[i - 1] 为正数时，最大乘积可以由当前元素与前一个位置的最大乘积（max[i - 1] 为正）相乘得到，同时也可能是当前元素本身（max[i - 1]为负）；最小乘积同理。当前元素 nums[i - 1] 为负数时，最大乘积可以由当前元素与前一个位置的最小乘积（min[i - 1]为负）相乘得到，同时也可能是当前元素本身（min[i - 1] 为正）：
   情况一：nums[i - 1]为负数，min[i - 1]是负数，min[i - 1] * nums[i - 1]为最大的正数。
   情况二：nums[i - 1]为负数，min[i - 1]是正数，nums[i - 1]为最大的正数。
   情况三：nums[i - 1]是正数，max[i - 1]是负数，nums[i - 1]为最大的正数。
   情况四：nums[i - 1]是正数，max[i - 1]是正数，max[i - 1] * nums[i - 1]为最大的正数。
3. 因此，设计两个数组 max 和 min，分别用于跟踪以当前位置结束的连续子数组的最大乘积和最小乘积。然后，在每次迭代中，根据当前元素的正负情况，更新 max[i] 和 min[i]，最终得到数组中连续子数组的最大乘积。

三、代码示例：

class Solution {public int maxProduct(int[] nums) {int result = Integer.MIN_VALUE;int[] max = new int[nums.length + 1];int[] min = new int[nums.length + 1];min[0] = 1;max[0] = 1;for(int i = 1; i <= nums.length; i++) {//情况一：nums[i - 1]为负数，min[i - 1]是负数，min[i - 1] * nums[i - 1]为最大的正数//情况二：nums[i - 1]为负数，min[i - 1]是正数，nums[i - 1]为最大的正数//情况三：nums[i - 1]是正数，max[i - 1]是负数，nums[i - 1]为最大的正数//情况四：nums[i - 1]是正数，max[i - 1]是正数，max[i - 1] * nums[i - 1]为最大的正数max[i] = Math.max(min[i - 1] * nums[i - 1], Math.max(nums[i - 1], max[i - 1] * nums[i - 1]));min[i] = Math.min(max[i - 1] * nums[i - 1], Math.min(nums[i - 1], min[i - 1] * nums[i - 1]));result = Math.max(result, max[i]);}return result;}
}

下面对代码进行分析：

1. 创建了两个长度为 nums.length + 1 的数组 max 和 min，用于存储当前位置之前的最大乘积和最小乘积。
2. 初始时，max[0] 和 min[0] 均为1，用于处理空子数组的情况。
3. 使用一个循环遍历数组 nums，从索引 1 开始。
4. 在每次迭代中，更新 max[i] 和 min[i]：
   max[i] 表示以当前位置结束的连续子数组的最大乘积，它可以由以下三种情况中的最大值得出：
   ①当前元素 nums[i - 1] 乘以前一个位置的最小乘积 min[i - 1]；
   ②当前元素 nums[i - 1] 本身；
   ③当前元素 nums[i - 1] 乘以前一个位置的最大乘积 max[i - 1]。
   min[i] 表示以当前位置结束的连续子数组的最小乘积，它可以由以下三种情况中的最小值得出：
   ①当前元素 nums[i - 1] 乘以前一个位置的最小乘积 min[i - 1]；
   ②当前元素 nums[i - 1] 本身；
   ③当前元素 nums[i - 1] 乘以前一个位置的最大乘积 max[i - 1]。
5. 在每次迭代中，更新 result 为当前最大乘积 max[i] 与之前的最大乘积 result 中的较大值。
6. 最后，返回 result，即为数组中连续子数组的最大乘积。

• 时间复杂度：该算法的时间复杂度为 O(n)，其中 n 为数组 nums 的长度。因为只需遍历一次数组，并在每个位置上执行常数时间的操作。

进一步简化空间复杂度，利用两个int型变量代替数组 max 和 min：

class Solution {public int maxProduct(int[] nums) {int result = Integer.MIN_VALUE;int max = 1;int min = 1;for(int i = 0; i < nums.length; i++) {int temp = max;max = Math.max(min * nums[i], Math.max(nums[i], max * nums[i]));min = Math.min(temp * nums[i], Math.min(nums[i], min * nums[i]));result = Math.max(result, max);}return result;}
}

这篇关于leetcode热题HOT 152. 乘积最大子数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---