题解 | #最大子矩阵#

暴力：o（n^4），遍历每一个点及其对应的1到i,1到j的所有点。

前缀和优化：o（n^3），同理先算出前缀和，考虑如何利用前缀和来减少一个变量的遍历。

可知前缀和[l,r]=sum[r]-[l-1],此时已经确定了上下俩个点的之间的一维区间，那只需要将其往没有累积的方向逐个扩展即可。

for(int l=1;l<=n;++l){

        for(int r=l;r<=n;++r){

            for(int i=1;i<=n;++i){

                ll t=sum[r][i]-sum[l-1][i];//区间和

                dp[i]=max(dp[i-1]+t,t);//dp[i]表示[l,r]往另一方向延伸至i的最大区间和，维护更新即可；

                maxn=max(maxn,dp[i]);

            }

        }

    }