Torus 二维最大矩阵的高效算法求解

Question

题：10827 - UVa Online Judge

Torus 上二维最大矩阵已知有能达 O(n^3) 的方法，不知有没有更高效的算法？

算法复杂度为 O(N^4)：

/*
 * Sai Cheemalapati
 * UVA 10827: Maximum sum on a torus
 * O(N^4) solution 
 */

#include<algorithm>
#include<cstdio>

using namespace std;

int T, N;
int A[500][500];

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &N);
        for(int i = 0; i < N * 2; i++) {
            for(int j = 0; j < N * 2; j++) {
                if(i < N && j < N) {
                    scanf("%d", &A[i][j]);
                    A[i + N][j] = A[i][j + N] = \
                        A[i + N][j + N] = A[i][j];
                }
                if(i > 0) A[i][j] += A[i - 1][j];
                if(j > 0) A[i][j] += A[i][j - 1];
                if(i > 0 && j > 0) A[i][j] -= A[i - 1][j - 1];
            }
        }
        int ans = -1000000;
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                for(int k = i; k < i + N; k++) {
                    for(int l = j; l < j + N; l++) {
                        int cur = A[k][l];
                        if(i > 0) cur -= A[i - 1][l];
                        if(j > 0) cur -= A[k][j - 1];
                        if(i > 0 && j > 0)
                            cur += A[i - 1][j - 1];
                        ans = max(ans, cur);
                    }
                }
            }
        }
        printf("%d\n", ans);
    }
}

Answer 1

你基本可以认为目前靠谱的做法是O(n3)的。
虽然有一些论文在数字上稍微更好了一点，但是实际意义似乎不大（可能和我读书少有关系）

如果你有兴趣（看起来你是竞赛选手应该不会有兴趣）可以看论文，比如这个
Algorithms for the maximum subarray problem based on matrix multiplication

不过这篇可能不好找，A Sub-cubic Time Algorithm for the k-Maximum Subarray Problem里面有一部分讲了那个算法，这篇好像好找pdf。。