Java DP Solution


  • 1

    We have following 3 variables for DP:

    1. pMax(i): maximum positive value if the sequence contains nums[i];
    2. nMin(i): minimum negative value if the sequence contains nums[i];
    3. optm: the optimal solution.

    Each time when we encounter a number nums[i], we first test if it is a non-negative number:
    Case nums[i] >= 0:
    pMax(i) = max(nums[i], pMax(i-1) * nums[i]);
    nMin(i) = nMin(i-1) * nums[i];

    Case nums[i] < 0:
    pMax(i) = nMin(i-1) * nums[i];
    nMin(i) = min(nums[i], pMax(i-1) * nums[i])

    So we can have the following code:
    ...

    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        
        int optm = nums[0];
        int pMax = nums[0] >= 0 ? nums[0] : 0;
        int nMin = nums[0] >= 0 ? 0 : nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] >= 0){
                pMax = Math.max(nums[i], pMax * nums[i]);
                nMin = nMin * nums[i];
            } else {
                int temp = Math.min(nums[i], pMax * nums[i]);
                pMax = nMin * nums[i];
                nMin = temp;
            }
            
            if (pMax > optm) {
                optm = pMax;
            }
        }
        
        return optm;
    }
    

    ...


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.