剑指Offer5

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

https://leetcode-cn.com/problems/maximum-product-subarray/solution/cheng-ji-zui-da-zi-shu-zu-by-leetcode-solution/

之前最大子序和思路，，不通过，因为情况处理未完全， dp[i] = Math.max(dp[i-1] * nums[i],nums[i]) 并不是最优子结构，如【[-2,3,-4]】的情况

class Solution {
    public int maxProduct(int[] nums) {
        if(nums.length == 1){
            return nums[0];
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        for(int i = 1;i 
1.双动态规划 
分析
 
最优子结构需要根据 负数的个数 判断，当出现负数，最大值和最小值将会互换
 
class Solution {
    public int maxProduct(int[] nums) {
        int max = Integer.MIN_VALUE, imax = 1, imin = 1; //一个保存最大的，一个保存最小的。
        for(int i=0; i 
2.根据负数的个数判断 
class Demo {
    public int maxProduct(int[] nums) {
        // 偶数个负数，整个数组为最大值
        // 奇数个负数，左边、右边取最大者
        int  max = Integer.MIN_VALUE;
        int temp = 1;
        // 从左往右, 取最大值
        for(int i=0; i=0; i--){
            temp = temp * nums[i];
            max = Math.max(max, temp);
            if(nums[i]==0) temp = 1;
        }
        return max;
    }
}