分归算法求最大邻接子阵列

假设有一个 $n \times m$ 的矩阵 $A$，我们要求出其中最大的邻接子阵列的和。

首先，我们需要定义什么是邻接子阵列。一个邻接子阵列是指在矩阵 $A$ 中，选取一列 $j$，并在这一列上选出一段连续的行 $i_1, i_2, \dots, i_k$，那么这段行和列 $j$ 形成的子矩阵就是一个邻接子阵列。

接下来，我们考虑使用分归算法来解决这个问题。我们可以将矩阵 $A$ 分成左右两个部分，分别求出左右两个部分的最大邻接子阵列的和。然后，我们还需要考虑跨越左右两个部分的邻接子阵列，也就是说，我们需要找到包含左右两个部分的邻接子阵列，求出这个邻接子阵列的和。

具体来说，我们可以从中间列开始，向左右两个方向扩展，记录下左边一段的最大子阵列和 $L$ 和右边一段的最大子阵列和 $R$，以及跨越中间列的最大邻接子阵列和 $M$。那么，整个矩阵的最大邻接子阵列和就是 $L, R, M$ 中的最大值。

接下来，我们考虑如何求出跨越中间列的最大邻接子阵列和 $M$。我们可以从中间列开始，向上下两个方向扩展，记录下上边一段的最大子阵列和 $U$ 和下边一段的最大子阵列和 $D$，以及跨越中间列的邻接子阵列和 $M'$。那么，跨越中间列的最大邻接子阵列和 $M$ 就是 $U + D - A_{mid}$，其中 $A_{mid}$ 是中间列的和。

最后，我们可以用分归算法求解整个问题。具体来说，我们可以递归地求解左右两个部分的最大邻接子阵列和，然后再求出跨越左右两个部分的邻接子阵列和，最后返回三者的最大值即可。

时间复杂度为 $O(nm \log m)$，因为我们需要递归 $\log m$ 层。