아름다운 행렬
시간 제한1초메모리 제한128 MB
N x N 행렬(N은 최대 400)에서 가능한 모든 정사각 부분 행렬 중 주대각선 합과 반대각선 합의 차이가 최대인 값을 구합니다.
문제
정사각 행렬의 아름다운 정도는 두 대각선 원소 합의 차이로 정한다.
왼쪽 위에서 오른쪽 아래로 내려가는 주 대각선 원소의 합을 A라고 하자. 오른쪽 위에서 왼쪽 아래로 내려가는 다른 대각선 원소의 합을 B라고 하자. 이 행렬의 아름다운 정도는 A - B이다.
N x N 행렬이 주어진다. 이 행렬에서 선택할 수 있는 모든 정사각 부분 행렬 중 아름다운 정도의 최댓값을 구하라. 1 x 1 부분 행렬은 두 대각선의 합이 같으므로 아름다운 정도가 0이다.
입력
첫째 줄에 행렬의 크기 N이 주어진다. (2 <= N <= 400)
다음 N개의 줄에는 N개의 정수가 공백으로 구분되어 주어진다. 각 원소는 -1000 이상 1000 이하이다.
출력
주어진 행렬에서 선택할 수 있는 모든 정사각 부분 행렬의 아름다운 정도 중 최댓값을 출력한다.