题解 | #最大子矩阵#

关于暴力的解题思路没什么可说的，无非是搜索模式的不同。

• 此题应该属于线性dp的一种变化，对于一位数组的连续子数组最大和的状态表达式是$dp[i]=max(dp[i-1]+v[i],v[i])dp[i]\; =\; max(dp[i-1]+v[i],v[i])$此题的变化在于将单值的v[i]转换为从$sum[i,j]sum[i,j]$，即$dp[k]=max(dp[k-1]+sum[i,j],sum[i,j])dp[k]\; =\; max(dp[k-1]+sum[i,j],sum[i,j])$,其中k表示矩阵的行标$sum[i,j]sum[i,j]$表示从下标i到下标j这一段的和。
• 时间复杂度$O(n^3)O(n^3)$,暴力大概需要接近$O(n^4)O(n^4)$

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<vector<int>> v(n, vector<int>(n));
    for(int i = 0; i< n; ++i){
        for(int j = 0; j < n; ++j){
            cin>>v[i][j];

        }
    }
    int ans = INT_MIN;
    for(int i = 0; i < n; ++i){//开始下标i
        vector<int> sum(n, 0);
        for (int j = i; j < n; ++j){//结束下标j
            int b = -32767;//注意此处不要初始化过小导致溢出会出现无厘头结果
            for(int k = 0; k < n; ++k){//第k行
                sum[k] += v[k][j];
                b = max(b+sum[k], sum[k]);//空间优化后的状态方程
                ans = max(ans, b);//记录递推过程中的最大值即是最后的结果
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}