LeetCode - Maximum Product Subarray
Problem description
Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Example 1:
1
2
3
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
1
2
3
Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
Analysis
Note that the product would be always greater than the previous one only if it’s 0.
So we can use two variable, one store the max > 0, another stores the min <0. So than if we meet an negative value, we can use min * v to get a new max > 0.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int maxProduct(int[] nums) {
if (nums == null){
return 0;
}
int max = nums[0];
int min = nums[0];
int res = nums[0];
for (int i = 1; i< nums.length; i++){
int v = nums[i];
int premax = max;
max = Math.max(v, Math.max(max *v, min *v));
min = Math.min(v, Math.min(premax *v, min * v));
res = Math.max(res, max);
}
return res;
}
What to improve
- don’t think 2d DP at the first time. Find out if there’s any other simple solution.