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;
}
}