Easy O(n) dp solution runs in 1ms beats 98%


  • 0
    M

    There are two steps involved in this solution:

    1. Run through the whole array and multiply all the numbers and find the max. If there is a 0, restart the product from the next number.
    2. Find the first negative number and divide all subsequent numbers from this number and check for the maximum product. If you find a 0, restart from the first negative number you find. This is to make sure that we account for the odd number of negative numbers in a series to find the max value.

    P.S: This could have been programmed better, but i was a bit frustrated when i wrote this code.

    public class Solution {
        public int maxProduct(int[] nums) {
         if(nums==null || nums.length==0){
             return 0;
         }
         if(nums.length==1){
             return nums[0];
         }
         int[] dp = new int[nums.length];
         int max=Integer.MIN_VALUE;
         for(int i=0; i<dp.length;i++){
             if(nums[i]==0){
                 dp[i]=0;
                 if(i+1<dp.length){
                     dp[i+1]=nums[i+1];
                     if(dp[i+1]>max){
                         max=dp[i+1];
                     }
                 }
                 i++;
                 continue;
             }
             if(i==0 || (dp[i-1]==0)){
                 dp[i]=nums[i];
             }else{
                dp[i]=dp[i-1]*nums[i];    
             }
             
             if(dp[i]>max){
                 max=dp[i];
             }
         }
         boolean b=false;
         int neg=0;
         for(int i=0; i<dp.length; i++){
             if(dp[i]<0 && !b){
                 b=!b;
                 neg=i;
             }
             else if(dp[i]==0){
                 if(0>max){
                     max=0;
                 }
                 b=false;
             }
             else if(b){
                 if((dp[i]/dp[neg])>max){
                     max = dp[i]/dp[neg];
                 }
             }
         }
         return max;
        }
    }
    

Log in to reply
 

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