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

---