Share my Java solution with expanation, O(N) time and O(1) space


  • 2
    O

    This problem is similar to #53 Max subarray, so using DP is my first choise.
    The difference is that we product each # instead of adding, which leads to a new situation, neg * neg = positive
    Let max[i] = the maxumum product ends with nums[i], and min[i] = the minimum product ends with nums[i]
    then we have:
    max[i] = max(nums[i], nums[i]*max[i-1], nums[i]*min[i-1])
    min[i] = min(nums[i], nums[i]*max[i-1], nums[i]*min[i-1])

    The max[i] and min[i] are only used once, so we can use two variable to store them.

    Here is the solution:

    public int maxProduct(int[] nums) {
        if(nums.length==0) return 0;
        int curMax = nums[0];
        int curMin = nums[0];
        int max = nums[0];
        for(int i = 1; i < nums.length; i++){
            int tempMax = nums[i]*curMax;
            int tempMin = nums[i]*curMin;
            curMax = max(nums[i], tempMax, tempMin);
            curMin = min(nums[i], tempMax, tempMin);
            max = Math.max(max, curMax);
        }
        return max;
    
    }
    private int max(int a, int b, int c){
        int r = Math.max(a,b);
        r = Math.max(r,c);
        return r;
    }
    private int min(int a, int b, int c){
        int r = Math.min(a,b);
        r = Math.min(r, c);
        return r;
    }

Log in to reply
 

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