LEETCODE 152. Maximum Product Subarray 解题思路分析

题目大意：

乘积最大子序列

给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

示例 1:

输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=152

解题思路分析：

本题是 LEETCODE 53. Maximum Subarray 解题思路分析 的加强版本，之前一题是求最大区间和，而本题是求最大区间乘积。两题最本质的区别是在对负数的处理上，求和时，加上一个负数，总和一定变小，而乘上一个负数，结果可能变大也可能变小（负数乘以负数结果会变大）。因此我们需要新建2个变量，一个代表区间内最大乘积max，另一个代表区间内最小乘积min，首元素区间的最大乘积与最小乘积均为该数字本身。我们从数组第二个数字开始循环，当前数字与前区间能形成的最大乘积，一定在下面三个元素中产生：

1. 当前数字num自身
2. 当前数字num * max
3. 当前数字num * min

用三个数的最大值更新max，最小值更新min，用max更新全局最大区间乘积，然后继续向后循环，找到一个全局最大区间乘积即可。

实现代码：

public int maxProduct(int[] nums) {
    int max=nums[0]; // 当前区间最大乘积
    int min=nums[0]; // 当前区间最小乘积
    int res=max; // 最大区间乘积
    // 从下标1开始循环所有数字
    for(int i=1;i<nums.length;i++){
        int n=nums[i]; // 当前数字
        int ma=n*max; // 当前数字乘以最大乘积
        int mi=n*min; // 当前数字乘以最小乘积
        max=Math.max(n,Math.max(ma,mi)); // 更新最大乘积
        min=Math.min(n,Math.min(ma,mi)); // 更新最小乘积
        res=Math.max(res,max); // 更新最大区间乘积
    }
    return res;
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 98.11% of Java online submissions for Maximum Product Subarray.

Memory Usage: 41.2 MB, less than 8.54% of Java online submissions for Maximum Product Subarray

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-152-maximum-product-subarray-解题思路分析/