Accepted C#, 155ms, O(n) .


  • 0
    R
        public int MaxProduct(int[] nums)
        {
            if (nums == null)
            {
                return 0;
            }
    
            if (nums.Length == 1)
            {
                return nums[0];
            }
    
            int max = nums[0];
            bool hasZero = false;
            List<int> subNums = new List<int>();
            for (int i = 0; i < nums.Length; i++)
            {
                if (nums[i] == 0)
                {
                    hasZero = true;
                    if (subNums.Count > 0)
                    {
                        max = Math.Max(max, MaxProductForList(subNums));
                        subNums = new List<int>();
                    }
                }
                else
                {
                    subNums.Add(nums[i]);
                }
            }
    
            if (subNums.Count > 0)
            {
                max = Math.Max(max, MaxProductForList(subNums));
            }
    
            if (max < 0 && hasZero)
            {
                max = 0;
            }
    
            return max;
        }
        
        public int MaxProductForList(List<int> nums)
        {
            if (nums.Count == 1)
            {
                return nums[0];
            }
    
            // calculate left minus part
            int firstMinusIndex = -1;
            int leftMinusProduct = 0;
            int temp = 1;
            for (int i = 0; i < nums.Count; i++)
            {
                temp *= nums[i];
                if (temp < 0)
                {
                    leftMinusProduct = temp;
                    firstMinusIndex = i;
                    break;
                }
            }
    
            // if no minus number at all, return the entire piece
            if (firstMinusIndex == -1)
            {
                return temp;
            }
    
            // calculate right minus part
            int lastMinusIndex = -1;
            int rightMinusProduct = 0;
            temp = 1;
            for (int j = nums.Count - 1; j >= 0; j--)
            {
                temp *= nums[j];
                if (temp < 0)
                {
                    rightMinusProduct = temp;
                    lastMinusIndex = j;
                    break;
                }
            }
    
            // if contains only 1 minus number
            if (firstMinusIndex == lastMinusIndex)
            {
                return Math.Max(leftMinusProduct / nums[firstMinusIndex], rightMinusProduct / nums[firstMinusIndex]);
            }
    
            // if contains 2 minus numbers
            int middleProduct = 1;
            for (int i = firstMinusIndex + 1; i <= lastMinusIndex - 1; i++)
            {
                middleProduct *= nums[i];
            }
            
            if (middleProduct > 0)
            {
                return leftMinusProduct * middleProduct * rightMinusProduct;
            }
            else
            {
                return leftMinusProduct < rightMinusProduct ? leftMinusProduct * middleProduct : rightMinusProduct * middleProduct;
            }
        }

Log in to reply
 

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