顿搜
飞过闲红千叶，夕岸在哪
类目归类
[LeetCode 152] Maximum Product Subarray [Java] [Runtime : 2MS]
10/15
1. Description
Find the contiguous subarray within an array (containing at least one number) which has the largest product.
2. Runtime Distribution
3. Submission Details
4. Example
given the array [2,3,-2,4]
the contiguous subarray [2,3] has the largest product = 6.
5. Explanation
[tabby title="DP"]
Let dpMax[i] stands for the max product which the contiguous subarray end at i.
Let dpMin[i] stands for the min product which the contiguous subarray end at i.
(1)、$$dpMax[0] = dpMin[0] = nums[0]$$
(2)、$$for(i : 1 \\rightarrow N)$$
$$temp1 = dpMax[i - 1] \\times nums[i];$$
$$temp2 = dpMin[i - 1] \\times nums[i];$$
$$dpMax[i] = max \\{ temp1, temp2, nums[i] \\};$$
$$dpMin[i] = min \\{ temp1, temp2, nums[i] \\};$$
[tabbyending]
6. Code
public class LeetCode0152 {
public int maxProduct(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int min = nums[0];
int max = nums[0];
int result = max;
for (int i = 1; i < nums.length; i++) {
int small = min * nums[i];
int large = max * nums[i];
if (large < small) {
int tmp = large;
large = small;
small = tmp;
}
min = Math.min(small, nums[i]);
max = Math.max(large, nums[i]);
if (max > result) {
result = max;
}
}
return result;
}
public static void main(String[] args) {
int nums[] = { 2, 3, -2, 4 };
LeetCode0152 leetcode = new LeetCode0152();
System.out.println(leetcode.maxProduct(nums));
}
}
