蒙吉数组

在应用于计算机科学的数学中，蒙吉数组或蒙吉矩阵是以其发现者法国数学家加斯帕德-蒙吉命名的数学对象。因此，对于一个Monge数组（2×2的子矩阵）的任何两行和两列，交点处的四个元素具有这样的特性：左上和右下元素之和（跨越主对角线）小于或等于左下和右上元素之和（跨越反对角线）。这个矩阵是一个Monge数组。左上和右下元素之和小于或等于左下和右上元素之和。任何从原始Monge数组中选择某些行和列而产生的子数组本身就是一个Monge数组。任何具有非负系数的Monge数组的线性组合本身就是一个Monge数组。Monge数组的一个有趣的特性是，如果你用圆圈标记每一行的最左边的最小值，你会发现你的圆圈向右下移；也就是说，如果f(x)=arg.对称的是，如果你在每一列的最上端标记最小值，你的圆圈将向右和向下行进。行和列的xxx值以相反的方向行进：向上向右，向下向左。弱蒙奇数组的概念已经被提出；弱蒙奇数组是一个n乘n的方形矩阵，每个Monge数组都是完全单调的，这意味着它的行最小值出现在一个非递减的列的序列中，而且对每个子数组来说，同样的属性也是如此。

这一特性使我们可以通过SMAWK算法快速找到行最小值。Monge矩阵只是两个离散变量的次模函数的另一个名称。准确地说，当且仅当A[i,j]是变量i,j的子模态函数时，A就是一个Monge矩阵。应用一个正方形的Monge矩阵，如果在其主对角线上也是对称的，则称为Supnick矩阵。