面试矩阵相关题（持续更新）

矩阵

给定一个有序矩阵，有正，有负，有0，求子矩阵的最大值：

暴力递归：时间是O（N^6）-->N^2(左上角点的位置数)xN^2（右下角点的位置数）xN^2（遍历一遍画出来的点的时间）

最好的解法是O(N^3)：在按排计算的时候用i，j进行遍历，然后通过使用求最大子数组的方法求出每次的子矩阵的最大值。

当为m（m<n） x n的时候，可以转置矩阵，让小的来做i和j的循环，这样为m^2 X n。

 

给定一个有序矩阵，有正，有负，有0，给定一个值k，求累加和小于等于k的最大子矩阵，矩阵大小用其中的元素个数来衡量：

和上题一样，只是每次比较一次即可。所需要的算法原型是：得到一个数组中不大于k的最长子数组的长度，在数组中有讲。

 

给定一个无序矩阵，只有0和1两种值，求只含有1的最大子矩阵的大小，大小按照其包含的元素个数来表示（略难）（时间复杂度）：