面试题库 › 算法 / 大模型 › 买卖股票的最佳时机 IV(最多 k 次交易)

买卖股票的最佳时机 IV(最多 k 次交易)

难度 ★★★在 1 场真实面经中被问到 方向:算法 / 大模型考点:动态规划

哪些公司问过

字节跳动1

常见岗位:推荐搜索广告

答案要点

  1. 状态:buy[j] 为最多 j 次交易且持股的最大收益,sell[j] 为不持股
  2. 转移:buy[j] = max(buy[j], sell[j−1] − p),sell[j] = max(sell[j], buy[j] + p)
  3. 初始 buy 为负无穷、sell 为 0,答案为 sell[k]
  4. 滚动数组:时间 O(nk),空间 O(k)
  5. k ≥ n/2 时等价于不限次数,累加所有上涨差价 O(n)

易错点

面试官常见追问

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

相关面试题