LeetCode152：动态规划求最大乘积子数组

LeetCode152给你一个整数数组nums请你找出数组中乘积最大的非空连续 子数组该子数组中至少包含一个数字并返回该子数组所对应的乘积。测试用例的答案是一个32-位整数。请注意一个只包含一个元素的数组的乘积是这个元素的值。示例 1:输入:nums [2,3,-2,4]输出:6解释:子数组 [2,3] 有最大乘积 6。示例 2:输入:nums [-2,0,-1]输出:0解释:结果不能为 2, 因为 [-2,-1] 不是子数组。Python解法贪心分段遍历class Solution: def maxProduct(self, nums: List[int]) - int: max_p nums[0] # 全局最大乘积初始为第一个元素 first_neg 0 # 记录分段里第一个负数的累计乘积0本段还没出现负数 pre_p 1 # 当前段连续乘积初始乘积基数1 for num in nums: pre_p pre_p * num # 累乘当前数字更新本段连续乘积 max_p max(max_p, pre_p) # 先拿当前总乘积更新最大值 # 情况1乘积为负且本段第一次出现负数 → 保存这个负数乘积 if pre_p 0 and first_neg 0: first_neg pre_p # 情况2本段已经有过负数现在又算出负乘积 # 删掉【第一个负数及前面所有数】只保留第一个负数之后的子数组乘积 elif pre_p 0: max_p max(max_p, int(pre_p / first_neg)) # 遇到0子数组被截断清空本段所有标记重新开新段 if num 0: pre_p 1 first_neg 0 return max_p以[2, -3, -4, -5, 6]为例展示过程核心逻辑Java解法贪心分段遍历public class Solution { public int maxProduct(int[] nums) { int max_p nums[0]; int first_neg 0; long pre_p 1; // long 防止乘积溢出 for (int num : nums) { pre_p pre_p * num; max_p Math.max(max_p, (int) pre_p); if (pre_p 0 first_neg 0) { first_neg (int) pre_p; } else if (pre_p 0) { int temp (int)(pre_p / first_neg); max_p Math.max(max_p, temp); } if (num 0) { pre_p 1; first_neg 0; } } return max_p; } }C解法贪心分段遍历class Solution { public: int maxProduct(vectorint nums) { int max_p nums[0]; int first_neg 0; long long pre_p 1; for (int num : nums) { pre_p * num; max_p max(max_p, (int)pre_p); if (pre_p 0 first_neg 0) { first_neg static_castint(pre_p); } else if (pre_p 0) { int temp static_castint(pre_p / first_neg); max_p max(max_p, temp); } if (num 0) { pre_p 1; first_neg 0; } } return max_p; } };