又是一题动态规划，一维dp数组。求子数组最大乘积，在线debug

在线debug

一维dp数组的题目面试必考。我已经写了好多题。 看到这种题目基本想到用动态规划。

再回顾一下动态规划，就是自下向上。先求解子问题。用dp数组保存每一个状态。这里写了一下这题。但是没有ac 100%

class Solution {
    public int maxProduct(int[] nums) {
        //想到了动态规划。。。
        //dp[i] 表示0-i 位置存储最大的值。。。如果没有，就保持num[i]
        //子数组是连续的。子序列是可以不连续的。

        int dp[] = new int[nums.length];
        
        //dp数组不能默认为0， 这里是相乘。
        Arrays.fill(dp, 1);
        dp[0] = nums[0];

        int res = Integer.MIN_VALUE;
        for(int i = 1; i< nums.length; i++){
            dp[i] = Math.max(dp[i-1]*nums[i], nums[i]);//至少包含一个数字，那就是自己。
            res = Math.max(dp[i], res);//放回dp 数组的最大值。
        }

        return res;


    }
}

在线debug

if(nums.length == 1){

return dp[0];//提前结束

}

dp[i] = Math.max(dp[i-1]*nums[i], nums[i]);//至少包含一个数字，那就是自己。

//这里少考虑了，前面是负数， 后面又有一个负数，这样会负负得正啊。。。

// [-2,3,-4] 预期结果：24,,, 但是我的写法只会输出3

class Solution {
    public int maxProduct(int[] nums) {
        //想到了动态规划。。。
        //dp[i] 表示0-i 位置存储最大的值。。。如果没有，就保持num[i]
        //子数组是连续的。子序列是可以不连续的。

        int dp[] = new int[nums.length];
        int dp2[] = new int[nums.length];
        
        //dp数组不能默认为0， 这里是相乘。
        Arrays.fill(dp, 1);
        dp[0] = nums[0];
        dp2[0] = nums[0];

        if(nums.length == 1){
            return dp[0];//提前结束
        }

        int res = Integer.MIN_VALUE;
        for(int i = 1; i< nums.length; i++){
            dp[i] = Math.max(dp[i-1]*nums[i], Math.max(nums[i]*dp2[i-1], nums[i]));//至少包含一个数字，那就是自己。
            //这里少考虑了，前面是负数， 后面又有一个负数，这样会负负得正啊。。。
            // [-2,3,-4]   预期结果：24,,,但是我的写法只会输出3 
            dp2[i] = Math.min(dp2[i-1]*nums[i], nums[i]);

            res = Math.max(dp[i], res);//放回dp 数组的最大值。
        }

        return res;//如果只有一个数组。这样放回res ==  Integer.MIN_VALUE;
        
    }
}

debug修改了一下：

加了一个dp2[i] : 这个用来保存最小值。 就是负数。 然后

dp[i] = Math.max(dp[i-1]*nums[i], Math.max(nums[i]*dp2[i-1], nums[i]));

在这里面选择最大的。有三个值要比较。 这样通过率提高了，但是还不是100%

参考一下大佬的：

class Solution {
    public int maxProduct(int[] nums) {
        int max = Integer.MIN_VALUE, imax = 1, imin = 1;
        for(int i=0; i<nums.length; i++){
            if(nums[i] < 0){ 
              int tmp = imax;
              imax = imin;
              imin = tmp;
            }
            imax = Math.max(imax*nums[i], nums[i]);
            imin = Math.min(imin*nums[i], nums[i]);
            
            max = Math.max(max, imax);
        }
        return max;
    }
}

// 作者：guanpengchn
// 链接：https://leetcode-cn.com/problems/maximum-product-subarray/solution/hua-jie-suan-fa-152-cheng-ji-zui-da-zi-xu-lie-by-g/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。