Leetcode 乘积最大子数组
该算法的目的是求出一个整数数组中乘积最大的连续子数组。
算法思想：
-
问题分析：
我们需要在数组中找到连续的子数组，使得该子数组的乘积最大。这个问题类似于“最大子序和”，但乘积相比求和有更多的复杂性，特别是当数组中包含负数或零时。负数会影响乘积的结果，因为两个负数相乘会变成正数，而零会将乘积变为0。因此，我们需要追踪子数组的最大值和最小值。 -
使用两个变量追踪最大最小乘积：
在遍历数组时，我们不仅需要记录当前子数组的最大乘积，还需要记录当前子数组的最小乘积。因为负数的存在，当前元素可能与前面的最小乘积相乘得到更大的结果。所以我们需要同时追踪最大乘积和最小乘积。maxProduct: 当前最大乘积minProduct: 当前最小乘积
-
动态更新最大最小乘积：
对于每个元素，我们更新maxProduct和minProduct，分别表示以当前元素结尾的最大和最小连续子数组的乘积。-
如果当前数字是负数，那么
maxProduct和minProduct需要交换，因为负数会将最大值变成最小值，反之亦然。 -
然后，我们通过以下公式更新它们：
maxProduct = Math.max(当前元素, 当前元素 * maxProduct)minProduct = Math.min(当前元素, 当前元素 * minProduct)
这意味着，
maxProduct要么是当前元素自己，要么是当前元素乘以之前的最大乘积。同样地，minProduct是当前元素本身或者它与之前最小乘积的乘积。
-
-
保持全局最大值：
我们还需要一个变量result来记录全局的最大乘积，即遍历过程中所有maxProduct的最大值。
关键点：
- 处理负数：当当前数字是负数时，我们交换
maxProduct和minProduct，因为负数可能会将之前的最大值变成最小值，最小值变成最大值。 - 零的影响：在计算时，我们总是将当前元素与之前的最大或最小乘积进行比较，这意味着如果遇到0或负数，算法也能处理好，确保重新从当前元素开始计算新的乘积。
- 时间复杂度：该算法的时间复杂度是 O(n)，因为我们只需遍历数组一次即可完成所有的计算。
总之，这个算法通过动态更新最大和最小乘积，并在遍历过程中追踪全局最大值，成功解决了乘积最大子数组的问题。
class Solution {
public int maxProduct(int[] nums) {
//由于负数的存在，所以同时需要记录当前最小乘积,
//如果数组长度为 1 时, nums[0]既是最大乘积也是最小乘积，也是最终的结果
int maxProduct = nums[0];
int minProduct = nums[0];
int result = nums[0];
for(int i = 1; i < nums.length; ++i) {
int current = nums[i];
//若当前元素是负数则需要交换最大最小乘积
if(current < 0) {
int temp = maxProduct;
maxProduct = minProduct;
minProduct = temp;
}
//更新最大乘积和最小乘积
//由于前面已经对负数单独处理过，所以这里的 maxProduct 始终是最大乘积
//此外，这两行代码会自动判断是否应当将子数组的起点重置为 current
maxProduct = Math.max(current, maxProduct * current);
minProduct = Math.min(current, minProduct * current);
//更新全局结果
result = Math.max(result, maxProduct);
}
return result;
}
}
原文地址：https://blog.csdn.net/coldasice342/article/details/142899965
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！