最大子数组乘积(动态规划)
哪些公司问过
答案要点
- 负数相乘可能变成最大,所以要同时维护以当前位置结尾的最大和最小乘积
- curMax = max(nums[i], curMax*nums[i], curMin*nums[i])
- curMin = min(nums[i], curMax*nums[i], curMin*nums[i])
- 更新前保存旧的 curMax,避免互相覆盖;每步更新全局答案
- 遇到 0 自然重新开始;时间 O(n),空间 O(1)
易错点
- 只维护最大值,忽略负数的情况
- 更新 curMax 后又用新值计算 curMin
- 没有处理数组为空或单元素
面试官常见追问
- 为什么要维护最小乘积?
- 怎么处理数组里有 0?
- 和最大子数组和有什么区别?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 最长递增子序列(LIS)27 场
- 动态规划的基础与解题流程26 场
- 爬楼梯(青蛙跳台阶)18 场
- 不同路径(网格路径数)17 场
- 买卖股票的最佳时机16 场
- 编辑距离的动态规划解法16 场
- 零钱兑换:最少硬币数与组合数12 场
- 最长公共子序列(LeetCode 1143)11 场
- 矩阵最小路径和(动态规划)10 场
- 斐波那契数列的几种解法8 场