求数组的最小子数组和
哪些公司问过
答案要点
- 状态 cur 表示以 a[i] 结尾的最小子数组和,cur = min(a[i], cur + a[i])
- 全局 ans 取所有 cur 的最小值,cur 和 ans 初始化为 a[0]
- 时间 O(n),空间 O(1)
- 边界:非空要求下全正数时答案为最小元素,允许为空则与 0 取小
- 等价解法:前缀和减去之前的最大前缀和,取最小
易错点
- 把 cur 和 ans 初始化为 0,导致全正数时错误返回 0
- 混淆子数组(连续)和子序列(可不连续)
- 大数累加溢出,int 不够时要用 long
面试官常见追问
- 如果要返回最小子数组的起止下标怎么做?
- 环形数组的最小子数组和怎么求?
- 求绝对值最大的子数组和怎么做?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 最长递增子序列(LIS)27 场
- 动态规划的基础与解题流程26 场
- 爬楼梯(青蛙跳台阶)18 场
- 不同路径(网格路径数)17 场
- 买卖股票的最佳时机16 场
- 编辑距离的动态规划解法16 场
- 零钱兑换:最少硬币数与组合数12 场
- 最长公共子序列(LeetCode 1143)11 场
- 矩阵最小路径和(动态规划)10 场
- 斐波那契数列的几种解法8 场