面试题库 › 算法 / 大模型 › 矩阵的最大非负积路径(LeetCode 1594)

矩阵的最大非负积路径(LeetCode 1594)

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

哪些公司问过

京东2

常见岗位:大模型算法、推荐搜索广告

答案要点

  1. 负数会让最小值变最大值,需同时维护到达每格的最大积和最小积
  2. g ≥ 0:mx = max(上mx, 左mx)·g,mn = min(上mn, 左mn)·g;g < 0 时交换来源
  3. 边界:首行只从左、首列只从上,起点 mx = mn = grid[0][0]
  4. 取模只在最后做,中间比较大小不能取模,用 64 位整数
  5. 时间 O(mn),空间可压缩为一维 O(n)

易错点

面试官常见追问

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

相关面试题