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

• 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;
}
}
``````

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