https://leetcode.cn/problems/maximum-product-subarray/?envType=study-plan-v2&envId=top-100-liked

152. 乘积最大子数组
已解答
中等
相关标签
相关企业
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 
子数组
（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

为了求得最大乘积，我们可以采用动态规划的思路。具体来说，我们需要维护两个变量：

max_so_far：当前遍历到的位置的最大乘积。
min_so_far：当前遍历到的位置的最小乘积（因为负数乘以负数可能变成正数）。
主要思想：
如果遇到正数，max_so_far 会乘以该数来增大乘积，min_so_far 会乘以该数来减少乘积。
如果遇到负数，max_so_far 会和 min_so_far 交换，因为负数与最小值相乘可能变成最大值，min_so_far 会乘以负数变得更加负。
如果遇到零，乘积会变成零，此时我们需要重置 max_so_far 和 min_so_far。

public class Solution {
    public int maxProduct(int[] nums) {
        // 初始化最大值和最小值
        int max_so_far = nums[0];
        int min_so_far = nums[0];
        int result = nums[0];
        
        // 从第二个元素开始遍历数组
        for (int i = 1; i < nums.length; i++) {
            // 如果当前元素是负数，交换最大值和最小值
            if (nums[i] < 0) {
                int temp = max_so_far;
                max_so_far = min_so_far;
                min_so_far = temp;
            }
            
            // 更新最大值和最小值
            max_so_far = Math.max(nums[i], max_so_far * nums[i]);
            min_so_far = Math.min(nums[i], min_so_far * nums[i]);
            
            // 更新结果
            result = Math.max(result, max_so_far);
        }
        
        return result;
    }
}