152. 乘积最大子数组

这是一个经典的动态规划问题。由于乘积的特殊性（负数相乘可能变成大正数），我们需要同时跟踪当前最大乘积和当前最小乘积。

public class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        // 初始化三个变量
        int maxSoFar = nums[0]; // 全局最大乘积
        int maxCurrent = nums[0]; // 以当前元素结尾的最大乘积
        int minCurrent = nums[0]; // 以当前元素结尾的最小乘积（可能是负数）

        // 从第二个元素开始遍历
        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];
            int tempMax = maxCurrent; // 保存旧值，用于计算minCurrent

            // 更新当前最大乘积：可能是当前数字本身，也可能是与前面最大/最小乘积的乘积
            maxCurrent = Math.max(num, Math.max(maxCurrent * num, minCurrent * num));

            // 更新当前最小乘积：考虑负数相乘变正数的情况
            minCurrent = Math.min(num, Math.min(tempMax * num, minCurrent * num));

            // 更新全局最大值
            maxSoFar = Math.max(maxSoFar, maxCurrent);
        }

        return maxSoFar;
    }
}

算法解析：

1. 核心思想：

   • 与最大子数组和不同，乘积问题需要考虑负数（两个负数相乘会变成正数）
   • 需要同时维护当前最大乘积和当前最小乘积
   • 全局最大乘积是遍历过程中的最大值

2. 动态规划状态定义：

   • maxCurrent：以当前元素结尾的子数组的最大乘积
   • minCurrent：以当前元素结尾的子数组的最小乘积（考虑负数情况）
   • maxSoFar：全局最大乘积（最终结果）

3. 状态转移方程：

   • maxCurrent = max(nums[i], maxCurrent*nums[i], minCurrent*nums[i])
   • minCurrent = min(nums[i], maxCurrent*nums[i], minCurrent*nums[i])
   • maxSoFar = max(maxSoFar, maxCurrent)

4. 复杂度分析：

   • 时间复杂度：O(n)，只需遍历数组一次
   • 空间复杂度：O(1)，只使用了常数级额外空间

这个解法巧妙地处理了负数和零的情况，能够正确找到最大乘积子数组，并且满足题目要求的时间和空间复杂度限制。