leetcode解题: Maximum Product Subarray (152)

发表于 | 分类于

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

解法：DP with O(N) time and O(1) space

由于有负数的存在，有可能负负得正的情况出现，所以需要维护当前的最大值和最小值。最大值是max(A[i], min A[i], max A[i])
同时对每一个新元素要update最大值和最小值。

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 || nums.length == 0) {
		return 0;
	}
	
	int min = nums[0];
	int max = nums[0];
	int res = nums[0];
	
	for (int i = 1; i < nums.length; i++) {
		int current_max = Math.max(max * nums[i], Math.max(min * nums[i], nums[i]));	
		int current_min = Math.min(max * nums[i], Math.max(min * nums[i], nums[i]));
		res = Math.max(res, current_max);
		// 要注意的是max和min需要同时update,不能先update一个再update另一个，因为计算max和min的公式中用到了对方
		max = current_max;
		min = current_min;
	}
	return res;
}