# Share my Java solution with expanation, O(N) time and O(1) space

• This problem is similar to #53 Max subarray, so using DP is my first choise.
The difference is that we product each # instead of adding, which leads to a new situation, neg * neg = positive
Let max[i] = the maxumum product ends with nums[i], and min[i] = the minimum product ends with nums[i]
then we have:
max[i] = max(nums[i], nums[i]*max[i-1], nums[i]*min[i-1])
min[i] = min(nums[i], nums[i]*max[i-1], nums[i]*min[i-1])

The max[i] and min[i] are only used once, so we can use two variable to store them.

Here is the solution:

``````public int maxProduct(int[] nums) {
if(nums.length==0) return 0;
int curMax = nums[0];
int curMin = nums[0];
int max = nums[0];
for(int i = 1; i < nums.length; i++){
int tempMax = nums[i]*curMax;
int tempMin = nums[i]*curMin;
curMax = max(nums[i], tempMax, tempMin);
curMin = min(nums[i], tempMax, tempMin);
max = Math.max(max, curMax);
}
return max;

}
private int max(int a, int b, int c){
int r = Math.max(a,b);
r = Math.max(r,c);
return r;
}
private int min(int a, int b, int c){
int r = Math.min(a,b);
r = Math.min(r, c);
return r;
}``````

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