面试题库 › Java 后端 › 求数组的最小子数组和

求数组的最小子数组和

难度 ★★☆在 1 场真实面经中被问到 方向:Java 后端考点:动态规划

哪些公司问过

字节跳动1

常见岗位:Java 后端

答案要点

  1. 状态 cur 表示以 a[i] 结尾的最小子数组和,cur = min(a[i], cur + a[i])
  2. 全局 ans 取所有 cur 的最小值,cur 和 ans 初始化为 a[0]
  3. 时间 O(n),空间 O(1)
  4. 边界:非空要求下全正数时答案为最小元素,允许为空则与 0 取小
  5. 等价解法:前缀和减去之前的最大前缀和,取最小

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题