java - 如何在随机生成的 4x4 网格中找到总和最高的 3x3 网格(取模网格，可以环绕)

Question

我解决这个问题的方法效率很低。

我的解决方案:我发现，对于 4x4 网格(2d 数组)中的每个值，3x3 网格的值都是中心。然后我将这个网格求和，添加到一个数组中，然后一旦找到每个 3x3 网格，我就会在新数组中找到最大的总和。

据我的教授说，这是“针对我们正在使用的网格大小的完美解决方案”。但是存在一个更有效的解决方案，他给了我提示

提示更有效的解决方案:“一个可能有用的提示:将其视为最大化二维积分，将网格视为(行，列)的函数。”

需要说明的是，我的解决方案获得了满分。我完全不知道如何开始编写更高效的解决方案。

Answer 1

这是 NxM 的通用解决方案网格 O(N * M)时间和空间。让我们假设网格有 NxM大小，我们必须找到 AxB总和最大的网格 (1 <= A <= N, 1 <= B <= M) .可以预先计算一个数组 sum(x, y) = 索引为 1 <= i <= x 的所有元素的总和和 1 <= j <= y ( sum(x, y) = sum(x - 1, y) + sum(x, y - 1) - sum(x - 1, y - 1) + a(x, y) ，其中 a 是初始网格)。那么答案就是max(sum(x, y) - sum(x, y - B) - sum(x - A, y) + sum(x - A, y - B))对于所有有效的 x和 y .此解决方案未考虑网格可以环绕但可以轻松修复的事实:使用新网格 2Nx2M看起来像:

aa
aa

上述算法找到的这个网格的答案就是最初环绕问题的答案。