当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.152.Maximum Product Subarray 最大连续子序列积

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


上一篇 LeetCode.628.Maximum Product of Three Numbers 数组中三个数的最大乘积

下一篇 LeetCode.160.Intersection of Two Linked Lists 两链表的交点

阅读
评论
474
阅读预计2分钟
创建日期 2020-02-04
修改日期 2020-05-18
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论