AFuture's Blog

抽屉原理简述：

第一抽屉原理：

1. 把多于n+k个的物体放到n个抽屉里，则至少有一个抽屉里的东西不少于两件。
2. 把多于mn(m乘以n)+1（n不为0）个的物体放到n个抽屉里，则至少有一个抽屉里有不少于（m+1）的物体。
3. 把无穷多件物体放入n个抽屉，则至少有一个抽屉里 有无穷个物体。

第二抽屉原理：

1. 把$（mn－1）$个物体放入n个抽屉中，其中必有一个抽屉中至多有$（m—1）$个物体 (例如，将3×5-1=14个物体放入5个抽屉中，则必定有一个抽屉中的物体数少于等于3-1=2)。

描述

一个M*N的矩阵，找到此矩阵的一个子矩阵，并且这个子矩阵的元素的和是最大的，输出这个最大的 值。例如：3*3的矩阵：

-1 3 -1
2 -1 3
-3 1 2

和最大的子矩阵是：

3 -1
-1 3
1 2

在数论中，裴蜀等式（Bézout's identity） 或 裴蜀定理 是一个关于最大公因数的定理：

对于正整数 a, b，存在s,t∈Z 使 sa + t b = gcd (a,b) 成立。