$O(N^2)$

分别按行、列、斜向遍历数组，找出和的最大值。

#include <bits/stdc++.h>
using namespace std;
const int N = 2010; 
long long a[N][N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); 
	int n;
	cin >> n;
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= n; ++j){
			cin >> a[i][j];
		}
	}
	long long res, ans = -1e18;
	//枚举取一行的情况
	for(int i = 1; i <= n; i++) {
	    res = 0;
	    for(int j = 1; j <= n; j++) res += a[i][j];
	    ans = max(ans, res);
	} 
	//枚举取一列的情况
	for(int i = 1; i <= n; i++) {
	    res = 0;
	    for(int j = 1; j <= n; j++) res += a[j][i];
	    ans = max(ans, res);
	} 
	//枚举从左上到右下的斜线的情况（同一条斜线上的差值相等） 
	//行和列的最小值都是 1，最大值都是 n，所以这个差值最小就是 1-n，最大是 n-1
	for(int i = 1-n; i <= n-1; i++) { //i枚举的是斜线的差值 
	    res = 0;
	    for(int j = 1; j <= n; j++) //枚举这条线上所有格子的行数 j 
	    //列是 j-i，还要判断范围，是因为要保证这个格子不能出界
	        if(j-i >= 1 && j-i <= n) res += a[j][j-i];
	    ans = max(ans, res);
	} 
	//枚举从右上到左下的斜线的情况（同一条斜线上的和相等）
	//行和列的最小值都是 1，最大值都是 n，所以这个和值最小就是 2，最大是 n+n
	for(int i = 2; i <= n+n; i++) { //i枚举的是斜线的和 
	    res = 0;
	    for(int j = 1; j <= n; j++)  //枚举这条线上所有格子的行数 j
	        //列是 i-j，还要判断范围，是因为要保证这个格子不能出界
	        if(1 <= i-j && i-j <= n) res += a[j][i-j];
	    ans = max(ans, res);
	}
	cout << ans; 
    return 0;
}