对于矩阵中所有值均为负的情况，此代码是否通过

Question

我正在阅读此面试问题及其解决方案，当给定矩阵中的所有值均为负值时，这种解决方案将失败，因为在这种情况下，输出将为零。有人可以确认这是真的吗？

这是链接：https://www.geeksforgeeks.org/find-the-maximum-cost-path-from-the-bottom-left-corner-to-the-top-right-corner/

Answer 1

它的确失败，因为额外的数组应该初始化为-INT_MIN。总体来说，这种解决方案非常糟糕，内存复杂度为O（n ^ 2），即使值可能尚未更新，它也总是使值排队。由于某些路径的权重可能超过int，因此它也可能遭受long值而不是int的额外数组的困扰。