https://leetcode.cn/problems/maximum-product-subarray/?envType=study-plan-v2&envId=top-100-liked
152. 乘积最大子数组
已解答
中等
相关标签
相关企业
给你一个整数数组 nums ,请你找出数组中乘积最大的非空连续
子数组
(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。测试用例的答案是一个 32-位 整数。
为了求得最大乘积,我们可以采用动态规划的思路。具体来说,我们需要维护两个变量:
max_so_far:当前遍历到的位置的最大乘积。
min_so_far:当前遍历到的位置的最小乘积(因为负数乘以负数可能变成正数)。
主要思想:
如果遇到正数,max_so_far 会乘以该数来增大乘积,min_so_far 会乘以该数来减少乘积。
如果遇到负数,max_so_far 会和 min_so_far 交换,因为负数与最小值相乘可能变成最大值,min_so_far 会乘以负数变得更加负。
如果遇到零,乘积会变成零,此时我们需要重置 max_so_far 和 min_so_far。
public class Solution {public int maxProduct(int[] nums) {// 初始化最大值和最小值int max_so_far = nums[0];int min_so_far = nums[0];int result = nums[0];// 从第二个元素开始遍历数组for (int i = 1; i < nums.length; i++) {// 如果当前元素是负数,交换最大值和最小值if (nums[i] < 0) {int temp = max_so_far;max_so_far = min_so_far;min_so_far = temp;}// 更新最大值和最小值max_so_far = Math.max(nums[i], max_so_far * nums[i]);min_so_far = Math.min(nums[i], min_so_far * nums[i]);// 更新结果result = Math.max(result, max_so_far);}return result;}
}