题目大意：
乘积最大子序列
给定一个整数数组 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，首元素区间的最大乘积与最小乘积均为该数字本身。我们从数组第二个数字开始循环，当前数字与前区间能形成的最大乘积，一定在下面三个元素中产生：
- 当前数字num自身
- 当前数字num * max
- 当前数字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-解题思路分析/