Function smawk::monge::is_monge

pub fn is_monge<T: Ord + Copy, M: Matrix<T>>(matrix: &M) -> bool
where
    Wrapping<T>: Add<Output = Wrapping<T>>,

Verify that a matrix is a Monge matrix.

A Monge matrix (or array) is a matrix where the following inequality holds:

M[i, j] + M[i', j'] <= M[i, j'] + M[i', j]  for all i < i', j < j'

The inequality says that the sum of the main diagonal is less than the sum of the antidiagonal. Checking this condition is done by checking n ✕ m submatrices, so the running time is O(mn).