my o(n) java solution,1ms, beats 98%


  • 0
    S
    public class Solution {
        public int maxProduct(int[] nums) {
            if (nums.length == 1)
                return nums[0];
            int first = 0, last = nums.length;
            int max = 0;
            int tempMax = 0;
            for (int i = 0; i < last; i++){
                if (nums[i] == 0){
                    tempMax = getMax(first,i,nums);
                    first = i+1;
                    max = max >= tempMax ? max : tempMax;
                }
            }
            tempMax = getMax(first,last,nums);
            max = max >= tempMax ? max : tempMax;
            return max;
        }
        private int getMax(int first, int last, int[] nums){
            if (first >= nums.length)
                return 0;
            if (first == last || last-first == 1)
                return nums[first];
            int[] temp = new int[5];
            Arrays.fill(temp, 1);
            int firstIndex = -1, lastIndex = -1;
            for (int i = first; i < last; i++){
                if (nums[i]<0){
                    temp[1] = nums[i];
                    firstIndex = i;
                    break;
                }
                else
                    temp[0] *= nums[i];
            }
            if (firstIndex == -1)
                return temp[0];
            for (int i = last-1; i > firstIndex; i--){
                if (nums[i] < 0){
                    temp[3] = nums[i];
                    lastIndex = i;
                    break;
                }
                else
                    temp[4] *= nums[i];
            }
            if (lastIndex == -1)
                return Math.max(temp[0], temp[4]);
            for(int i = firstIndex+1; i < lastIndex; i++)
                temp[2] *= nums[i];
            if (temp[2] < 0)
                return Math.max(temp[0]*temp[1]*temp[2],temp[2]*temp[3]*temp[4]);
            else
                return temp[0]*temp[1]*temp[2]*temp[3]*temp[4];
        }
    }
    

Log in to reply
 

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