152. 乘积最大子序列

>>强大,10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程!

本题来自 LeetCode:152. 乘积最大子序列[1]

题目详情

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

示例 1:

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

示例 2:

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

题目分析

  1. 定义max 为最大乘积,currentMax为当前最大乘积;
  2. 显然max = max(max, currentMax);
  3. 若数组nums全为正整数,则currentMax = currentMax * nums[i];
  4. 由于数组中存在0,故currentMax = max(currentMax * nums[i], nums[i]);
  5. 由于数组中存在负数,因此需要维护当前最小乘积currentMin:
    • currentMin < 0nums[i] > 0,则currentMin = min(currentMin * nums[i], nums[i])
    • currentMin > 0nums[i] < 0,则currentMin = min(currentMax * nums[i], nums[i])
    • currentMin < 0nums[i] < 0currentMin = min(currentMax * nums[i], nums[i]), currentMax = max(currentMin * nums[i], nums[i])

题目解答

class Solution {
public int maxProduct(int[] nums) {
int max = Integer.MIN_VALUE;

int currentMax = 1;
int currentMin = 1;
for(int i = 0; i < nums.length; i ++) {
if(nums[i] < 0) {
currentMax = currentMax ^ currentMin;
currentMin = currentMax ^ currentMin;
currentMax = currentMax ^ currentMin;
}

currentMax = Math.max(currentMax * nums[i], nums[i]);
currentMin = Math.min(currentMin * nums[i], nums[i]);

max = Math.max(max, currentMax);
}
return max;
}
}

进一步可观察可发现,currentMaxcurrentMin分别取这三个值currentMax * nums[i]currentMin * nums[i]nums[i]的最大值和最小值。调整代码后:

class Solution {
public int maxProduct(int[] nums) {
int max = Integer.MIN_VALUE;

int currentMax = 1;
int currentMin = 1;
for(int i = 0; i < nums.length; i ++) {
int tempMax = currentMax * nums[i];
int tempMin = currentMin * nums[i];

currentMax = Math.max(Math.max(tempMax, tempMin), nums[i]);
currentMin = Math.min(Math.min(tempMax, tempMin), nums[i]);

max = Math.max(max, currentMax);
}
return max;
}
}

参考资料

[1]

152. 乘积最大子序列: https://leetcode-cn.com/problems/maximum-product-subarray/


原文始发于微信公众号(xiaogan的技术博客):152. 乘积最大子序列