Kadane 算法在二维应用

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
ll n,m,ans,t;
ll a[505][505];
ll pre[505][505];
ll row[505];
const ll INF=1e18;
void main1()
{
  cin>>n>>m;
  for(int i=1;i<=n;++i)
    for(int j=1;j<=m;++j)
      cin>>a[i][j];
  ll ans=-INF;;
  for(int l=1;l<=m;l++)
  {
        memset(row,0,sizeof(row));
        for(int r=l;r<=m;r++)
        {
            ll sum=0;
            for(int i=1;i<=n;i++)
            {
                row[i]+=a[i][r];
                sum=max(sum+row[i],row[i]);
                ans=max(ans,sum);
            }
        }
    }
  cout<<ans;
}
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    main1();
    return 0;
} 

这个东西其实是最大子段和的变体

题目链接

以及一道和此本题差不多的题，就是数据水一点

题目链接

这个题如果用暴力解法的复杂度就是$O(n^2m^2)$的，题目的数据范围是$n<=500且m<=500$肯定过不了

我们先考虑第$i$行到第$j$行之间的最大子矩阵

$$\begin{bmatrix} a_{i,1} &a_{i,2} &a_{i,3} &a_{i,4}... & a_{i,m} \\ a_{i+1,1} &a_{i+1,2} &a_{i+1,3} &a_{i+1,4}... & a_{i+1,m}\\ ....& ....& ....& ....& ....\\ a_{j,1} &a_{j,2} &a_{j,3} &a_{j,4}... & a_{j,m} \end{bmatrix}$$

由于我们子矩阵的上下两行是确定的，假设我们最大子矩阵的左右两行分别是第$l$行或者是第$r$行可以发现，子矩阵的元素和等于第$l$列的第$i$行到第$j$行的列前缀和到第$r$列的第$i$行到第$j$行的列前缀和

于是我们可以对某两行之间的矩阵进行压维

$$\begin{bmatrix} pre_{1}&pre_{2}&pre_{3}&pre_{4}&pre_{5}& \end{bmatrix}$$

然后这个题就转化成最大子段和了，结束 下面附上代码块 解法就是$n^2$枚举两行并且$m$次枚举列 复杂度$O(n^2m)$提一嘴，一般一秒在cf评测机上可以运行2.5e8的数据

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[501][501];
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> s(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int v;
            cin >> v;
            s[i][j] = s[i - 1][j] + v;
        }
    }
    int mx = -2e18;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            int cur = 0;
            int mi = 0;
            for (int k = 1; k <= m; k++) {
                int val = s[j][k] - s[i - 1][k];
                cur += val;
                mx = max(mx, cur - mi);
                mi = min(mi, cur);
            }
        }
    }
    cout << mx << endl;
    return 0;
}