🌗 152. 乘积最大子数组

难度: 🌗

问题描述

---

解法

class Solution {
    public int maxProduct(int[] nums) {
        // 思路：
        // dp[len][2] - 分别保存最大正数 & 最小负数
        // singleMax 单独保存单个值的情况下最大值
        int len = nums.length;
        // 特殊情况特判
        if(len == 1) {
            return nums[0];
        }
        // len > 1
        int[][] dp = new int[len][2];
        if(nums[0] > 0) {
            dp[0][0] = nums[0];
        } else if(nums[0] < 0) {
            dp[0][1] = nums[0];
        }
        int singleMax = nums[0];
        int dpMax = nums[0];
        // dp
        for(int i = 1; i < len; i ++) {
            singleMax = Math.max(singleMax, nums[i]);
            if(nums[i] == 0) {
                dp[i][0] = 0;
                dp[i][1] = 0; 
            } else if(nums[i] > 0) {
                dp[i][0] = Math.max(dp[i - 1][0] * nums[i], nums[i]); // 若 dp[i - 1][0] == 0 那么乘积 == 0 < nums[i]
                dp[i][1] = dp[i - 1][1] * nums[i];
            } else {
                dp[i][0] = dp[i - 1][1] * nums[i];
                dp[i][1] = Math.min(dp[i - 1][0] * nums[i], nums[i]);
            }
            dpMax = Math.max(dpMax, dp[i][0]);
        }
        return Math.max(singleMax, dpMax);
    }
}

---

输出