java solution beats 88.26% with explanation


  • 0
    P

    //First we split the nums into several pieces according to the position of zeros, for example:[0,-1,2,-3,0,-4,-5,6,0,2,-3,5,-7,8,-9] is splitted into three subarrays:[-1,2,-3],[-4,-5,6],[2,-3,5,-7,8,-9].
    //Then we calculate each Maximum product subarray of the nums' subarrays([-1,2,-3],[-4,-5,6],[2,-3,5,-7,8,-9]).
    //The Maximum product subarray is calculated in this way:
    //1. Get the numbers of negative numbers in each subarray, for example, [-1,2,-3] has two negative numbers(-1,-3),and [2,-3,5,-7,8,-9] has three negative numbers(-3,-7,-9).
    //2. If the numbers of negative numbers is even, then the Maximum product subarray must be the array itself. For example, [-1,2,-3]'s Maximum product subarray is [-1,2,-3]. Its Maximum product is -1 * 2 * -3 = 6. Similarly, the Maximum product of [-4,-5,6] is 120.
    //3. If the numbers of negative numbers is odd, take [2,-3,5,-7,8,-9] as an example. We first get the whole product of this array: whole = 2* -3 * 5 * -7 * 8 * -9 = -15120, then we get the first and last negative numbers in the array(first negative is -3 and last is -9). we can devide the whole by the first negative number: whole1 = whole/(2*-3) = 2520(note that we must devide 2 at first, because the subarray must be contiguous), then we can devide the whole by the last negative number: whole2 = whole/(-9) = 1680. And we compare the whole1(2520) to whole2(1680). Then we can know that the 2520 is the Maxmium product of [2,-3,5,-7,8,-9].
    //4. Of course 2520>120(Maximum product of [-4,-5,6])>6(Maximum product of [-1,2,-3]). So the final result is 2520.
    //5. We should also take cases such as [-2,0,-1] or [0,-2,0] into consideration.
    //6. Thanks for reading (,• ₃ •,)

    public class Solution {
        public int maxProduct(int[] nums) {
            if(nums.length == 0)
            {
                return 0;
            }
            if(nums.length == 1)
            {
                return nums[0];
            }
            int beginpoint = 0;
            int lastpoint = 0;
            int max = Integer.MIN_VALUE;
            for(int i = 0;i<nums.length+1;i++)
            {
                
                if(i == nums.length||nums[i] == 0)
                {
                    lastpoint = i;
                    int temp = partmaxing(beginpoint,lastpoint,nums);
                    beginpoint = i+1;
                    if(temp>max)
                    {
                        max = temp;
                    }
                }
            }
            return Math.max(max,0);//for case such as:[-2,0,-1], we get max = -1. but the maximum is 0.
        }
        public int partmaxing(int beginpoint,int lastpoint,int[] nums)
        {
            if(beginpoint == lastpoint-1)
            {
                return nums[beginpoint];//for case such as:[-2,0,-1]
            }
            if(beginpoint == lastpoint)
            {
                return 0;//for case such as:[0,-2,0]
            }
            int count = 0;
            int whole = 1;
            Boolean firstnegetive = true;
            int first = 0;
            int last = 0;
            for(int i = beginpoint;i<lastpoint;i++)
            {
                if(nums[i]<0)
                {
                    count++;
                    if(firstnegetive)
                    {
                        first = i;
                        last = i;
                        firstnegetive = false;
                    }
                    else
                    {
                        last = i;
                    }
                }
                whole *= nums[i];
            }
            int whole1 = whole;
            int whole2 = whole;
            if(count%2 == 0)
            {
                return whole;
            }
            else
            {
                for(int i = beginpoint;i<lastpoint;i++)
                {
                    if(i!=first)
                    {
                        whole1 /= nums[i];
                    }
                    else
                    {
                        whole1 /= nums[i];
                        break;
                    }
                }
                for(int i = lastpoint-1;i>beginpoint-1;i--)
                {
                    if(i!=last)
                    {
                        whole2 /= nums[i];
                    }
                    else
                    {
                        whole2 /= nums[i];
                        break;
                    }
                }
                return Math.max(whole1,whole2);
            }
        }
    }
    

Log in to reply
 

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