Share my greedy O(1) space and O(n) time.


  • 1
    A

    the difference of this problem and the max sum subarray is that we may meet a negative number during traverse the array. My solution to deal with negative number is that we use two variable to store both the product include the negative number and not include it.
    example: if x < 0

     .............................. x
                ...................               //this part could be neg variable's product range
                      .............               //this part could be pos variable's product range
    
    public class Solution {
        public int maxProduct(int[] nums) {
            int max = nums[0];
            int pos = (nums[0] <= 0)? 1: nums[0];        //pos must be a positive number
            int neg = (nums[0] == 0)? 1: nums[0];        //neg could be positive or negative number. 
            for(int i = 1; i < nums.length; i++){
                int val = nums[i];
                if(val > 0){
                    pos *= val;
                    neg *= val;
                    max = Math.max(max, pos);
                }else if(val < 0){
                    if(neg < 0){
                        int temp = neg;
                        neg = pos * val;
                        pos = temp * val;    //exchange pos and neg's value after they times current negative number
                        max = Math.max(max, pos);
                    }else{
                        neg *= val;      //neg continue to multiply the future number by times this number
                        pos = 1;          //pos give up previous product, we start the pos's value over from the next number
                    }
                }else{
                    pos = 1;
                    neg = 1;
                    max = Math.max(max, 0);   //max == 0 when other solution are all negative
                }
            }
            return max;
        }
    }
    

Log in to reply
 

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