【算法日记】Day 8 动态规划专题——子数组最大累加和问题（二）

张开发
• 2026/4/15 4:18:54 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

【算法日记】Day 8 动态规划专题——子数组最大累加和问题（二）
Abstract#动态规划#一维DP#子数组1. 题目题目LeetCode 152. 乘积最大子数组核心思路由于负数的存在乘法会导致最大值变最小值、最小值变最大值。因此需要同时维护以当前元素结尾的子数组乘积最大值和最小值。遍历时当前元素nums[i]单独成段或与之前的最大/最小值相乘。状态转移curMax max(nums[i], max(prevMax * nums[i], prevMin * nums[i]))curMin min(nums[i], min(prevMax * nums[i], prevMin * nums[i]))复杂度时间复杂度O ( n ) O(n)O(n)空间复杂度O ( 1 ) O(1)O(1)。2. 代码classSolution{public:intmaxProduct(vectorintnums){intansnums[0];for(inti1,allMinnums[0],allMaxnums[0],curMax,curMin;inums.size();i){curMinmin(nums[i],min(allMin*nums[i],allMax*nums[i]));curMaxmax(nums[i],max(allMin*nums[i],allMax*nums[i]));allMincurMin;allMaxcurMax;ansmax(allMax,ans);}returnans;}};3. 心得忘记维护最小值如果只维护最大值遇到负数时会出错因为负数乘最小值可能变成最大值。例如[-2, 3, -4]只维护最大值会得到3实际应为24-23-4。必须同时维护最小值和最大值。状态转移的全面性curMax必须在nums[i]、prevMax*nums[i]、prevMin*nums[i]三者中取最大不能遗漏nums[i]自身当之前乘积为负且当前为正时重新开始更好。4. 相关题目LeetCode 面试题 17.24. 最大子矩阵

更多文章