LeetCode.152.Maximum Product Subarray 最大连续子序列积
题目描述
152 Maximum Product Subarray https://leetcode-cn.com/problems/maximum-product-subarray/
Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Example 1:
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
相似题目
LeetCode.053.Maximum Subarray 最大连续子序列和 LeetCode.152.Maximum Product Subarray 最大连续子序列积
解题过程
设 max(i) 是 a[0,...,i] 中以 a[i] 为结尾的(必须包含a[i])连续子序列的乘积最大值 min(i) 是 a[0,...,i] 中以 a[i] 为结尾的(必须包含a[i])连续子序列的乘积最小值 由于乘积的负负得正特性, 若 a[i] 是负值且 min(i-1) 也是负值,乘积可能诞生一个新的最大正值,这就是为什么我们还需要保存并不断更新一个乘积最小值。 可得递推公式:
$ max(i+1) = max(a[i+1], max(i) \times a[i+1], min(i) \times a[i+1]) \tag{1} $ $ min(i+1) = min(a[i+1], max(i) \times a[i+1], min(i) \times a[i+1]) \tag{2} $
从头到尾计算出 max(i) 和 min(i),计算过程中出现过的最大 max(i) 就是整个数组的 最大连续子序列积
时间复杂度 O(n)
空间复杂度 O(1)
private static class SolutiionV2020 {
public int maxProduct(int[] nums) {
int max = nums[0];
// nums[0,...,i] 中以nums[i]为结尾的连续子序列的乘积最大值
int maxi = nums[0];
// nums[0,...,i] 中以nums[i]为结尾的连续子序列的乘积最小值
int mini = nums[0];
for (int i = 1; i < nums.length; i++) {
// 保存原值,更新mini用
int oldMaxi = maxi;
maxi = Math.max(mini * nums[i], Math.max(maxi * nums[i], nums[i]));
mini = Math.min(oldMaxi * nums[i], Math.min(mini * nums[i], nums[i]));
max = Math.max(max, maxi);
}
return max;
}
}
GitHub代码
algorithms/leetcode/leetcode/_152_MaximumProductSubarray.java https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_152_MaximumProductSubarray.java