algorithm - 给定一个大小为 MxN 且具有正整数值的二维矩阵，找到具有最大和的闭环

Question

循环可以是任意形状，但只能向上/向下/向左/向右。循环的总和定义为沿其周边的所有唯一元素的总和。循环不允许自身交叉，因为那将是次优的(因为我们不允许对同一个元素计数两次)。

有谁知道可以在多项式时间内解决这个问题的方法吗？有人问我这个问题，但我不知道如何用 DP 或其他方式做到这一点。

编辑 - 循环也应该是凸的。

Answer 1

这是 DP 解决方案的概要。

对于每一对点，找到最大凸弧，如果它弯曲，则弯曲远离左下角。

对于每一对点，找到最大凸弧，如果它弯曲，则弯曲远离右上角。

找到这两条弧的总和最大的点对。那对弧就是你的答案。