Monge array란?

정의

$n \times m$인 matrix가 존재할 때, $A[i, j] + A[k, l] \leqq A[i.l] + A[k,l]$이면 monge array라고 한다.
( $1 \leqq i < k \leqq n and 1 \leqq j <l \leqq m$ )

위에 그림에서 빨간색합과 주황색의 합을 쳤을 때, 빨간색 $\leqq$ 주황색이 성립하면 monge array인 것이다.

특성

1. 특정한 row와 col를 선택해도 Monge array이다. (subarray도 동일)
2. Monge Array의 양수 지수승도 Monge Array이다. (subarray도 동일)
3. Monge array 두 개를 더해도 monge array이다.

증명
A, B가 Monge array, C = A + B 일 때,
$A[i, j] + A[k, l] \leqq A[i.l] + A[k,l]$
$B[i, j] + B[k, l] \leqq B[i.l] + B[k,l]$따라서, $C[i, j] + C[k, l] \leqq C[i.l] + C[k,l]$ 이다.

 

[참고]
https://en.wikipedia.org/wiki/Monge_array
https://justicehui.github.io/hard-algorithm/2020/04/30/monge-array/