M25570 洋葱

思路：

• 枚举 $1\le i\le \lceil \frac{n}{2}\rceil$，令 $j=n-i+1$，则第 $i$ 层包含以 $(i,i)$ 为左上角、以 $(j,j)$ 为右下角的正方形边框上的数。
• 对每一层，把这些数加起来，再取所有层中的最大值即可。
• 时间复杂度为 $O(n^2)$。

代码：

#include <stdio.h>

int a[101][101];

int main(){
	int n, mid, ans = 0;
	scanf("%d", &n);
	mid = (n + 1) / 2;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){
			scanf("%d", &a[i][j]);
		}
	}
	for (int i = 1, j = n; i <= mid; i++, j--){
		int cur_ans = 0;
		for (int k = i; k <= j; k++){
			cur_ans += a[i][k];
		}
		for (int k = i + 1; k <= j; k++){
			cur_ans += a[k][i];
		}
		if (i < j){
			for (int k = i + 1; k <= j; k++){
				cur_ans += a[j][k];
			}
			for (int k = i + 1; k < j; k++){
				cur_ans += a[k][j];
			}
		}
		if (ans < cur_ans) ans = cur_ans;
	}
	printf("%d", ans);
	return 0;
}