LeetCode152：乘积最大子数组

题目描述：

解题思路及答案：

采用动态规划来做，设dp[ i ]表示以nums[ i ]结尾的子数组的最大乘积，接下来开始分析最大乘积的来源：

1、负数相乘，得到最大乘积；

2、正数相乘，得到最大乘积；

因此，需要保存一下dp[ i - 1 ]的最大值和最小值。

// 维护一个最大值和一个最小值， 因为如果最小值是一个负的很多的值，然后再乘以一个负值，那么接下来它将成为最大值，因此需要维护一个最小值
class Solution {
    public int maxProduct(int[] nums) {
        int len = nums.length;
        if(len == 0 || nums == null) return 0;
        int max = nums[0];
        int min = nums[0];
        int ans = nums[0];
        for(int i = 1; i < len; i++){
            int maxtemp = max;
            max = Math.max(min * nums[i] , Math.max(nums[i] , nums[i] * max)); // 最大值是min * nums[i] （min 和 nums[i]都是负数的情况），或者nums[i] 或者 nums[i] * max
            min = Math.min(maxtemp * nums[i], Math.min(nums[i] , nums[i] * min)); // 最小值是maxtemp * nums[i] （maxtemp 和 nums[i]是异号的情况），或者nums[i] 或者 nums[i] * min
            ans = Math.max(max, ans); // 保存最大值
        }
        return ans;
    }
}