初十hu测 T1.max（最大子矩阵启发）

分析：
先看一下正解：

然而我用了另一种方法：
枚举上下两行（确定了子矩阵的上下范围）
之后处理出每一列两个数的min值
以下讨论都基于这个min值（实际上就是把同一列上的两个数绑定了）

因为我们只关心是否存在，不关心子矩阵到底长什么样
（存在即合理）
因此对于一个min值X，只要存在比ta大元素，X就可以作为子矩阵的价值
我们只要找到这些min值之中的第二大即可

看似是一个$O(n^3)$的算法
然而我们可以加一点优化：预处理出每一行的最大值$mx_i$
若$mx_i$小于当前得到的局部最优解
我们就没有必要枚举第i行了

tip

收到了最大子矩阵的启发
澍神说这是lrj的方法，蛮不错

#include<cstdio>
#include<cstring>
#include<iostream>using namespace std;const int INF=1e9;
int n,m,mp[1003][1003],mx[1003],ans;int main()
{freopen("max.in","r",stdin);freopen("max.out","w",stdout);scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) {mx[i]=-INF;for (int j=1;j<=m;j++) scanf("%d",&mp[i][j]),mx[i]=max(mx[i],mp[i][j]);}ans=-INF;for (int i=1;i<n;i++) if (mx[i]>ans)for (int j=i+1;j<=n;j++) if (mx[j]>ans) {int max1=-INF,max2=-INF;for (int k=1;k<=m;k++) {int t=min(mp[i][k],mp[j][k]);if (t>max1) max2=max1,max1=t;else if (t<max1&&t>max2)max2=t;}ans=max(ans,max2);}printf("%d",ans);return 0;
}