面试题库 › C++ / 后端 › 最大子数组和(LC53,动态规划)

最大子数组和(LC53,动态规划)

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

哪些公司问过

快手1游密科技1

常见岗位:音视频开发、C/C++ 软件开发

答案要点

  1. 求连续子数组最大和,用动态规划,dp[i] 为以 i 结尾的最大子数组和
  2. 转移 dp[i] = max(dp[i-1] + a[i], a[i]):前段和为负则从当前重新开始
  3. 答案是所有 dp[i] 的最大值,而非最后一个
  4. 全负数时结果是最大的单个元素,初值设为首元素或负无穷,不能设 0
  5. dp 只依赖前一状态,可滚动为一个变量,空间 O(1)、时间 O(n)(Kadane)

易错点

面试官常见追问

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

相关面试题