M02766: 最大子矩阵

binary, dp,kadane http://cs101.openjudge.cn/pctbook/M02766/

【姚博骞 25物院】思路：三种算法我都写了，其中分治比我想的难写很多，比一维要难，且复杂度只降到O(n^3log n) dp其实也包含了kadane的思想，无非是直接用kadane还是间接，两个方法的复杂度都是O(n^3)

#include<iostream>
#include<vector>
using namespace std;//kadane 算法
int max(int a,int b)
{
    return (a>b)?a:b;
}
int min(int a,int b)
{
    return(a<b)?a:b;
}
int juxing(int p,int q,int r,int s,vector<vector<int>>&qz)
{
    return qz[p][r]+qz[q][s]-qz[p][s]-qz[q][r];
}
int fenzhi(vector<vector<int>>&qz,int i1,int i2,int j1,int j2)
{
    int midi=0.5*(i1+i2);
    int midj=0.5*(j1+j2);
    int ans=-100000000;
    if((j2==j1)||(i2==i1)) return -10000000;
    if(i1!=i2)
    {
        int ans1=fenzhi(qz,i1,midi,j1,j2);
        int ans2=fenzhi(qz,midi+1,i2,j1,j2);
        ans=max(ans,max(ans1,ans2));
    }
    if(j1!=j2)
    {
        int ans1=fenzhi(qz,i1,i2,j1,midj);
        int ans2=fenzhi(qz,i1,i2,midj+1,j2);
        ans=max(ans,max(ans1,ans2));
    }
    int ans3,ans4;
    ans3=ans4=-100000000;
    for(int i=i1;i<=i2;i++)
    {
        for(int i_=i+1;i_<=i2;i_++)
        {
            int p,q;
            p=100000000;
            q=-100000000;
            for(int j=j1;j<=midj;j++)
            {
                p=min(p,juxing(i,i_,j1,j,qz));
            }
            for(int j=midj+1;j<=j2;j++)
            {
                q=max(q,juxing(i,i_,j1,j,qz));
            }
            ans3=max(q-p,ans3);
        }
    }
    for(int j=j1;j<=j2;j++)
    {
        for(int j_=j+1;j_<=j2;j_++)
        {
            int p,q;
            p=100000000;
            q=-100000000;
            for(int i=i1;i<=midi;i++)
            {
                p=min(p,juxing(i1,i,j,j_,qz));
            }
            for(int i=midi+1;i<=i2;i++)
            {
                q=max(q,juxing(i1,i,j,j_,qz));
            }
            ans4=max(q-p,ans4);
        }
    }
    ans=max(ans,max(ans3,ans4));
    return ans; 
}
int maxSubmatrix(vector<vector<int>>& a)
{
    int n = a.size();
    int m = a[0].size();
    int ans = -1e9;

    // 枚举上边界
    for(int top = 0; top < n; top++)
    {
        vector<int> sum(m, 0);  // 压缩后的数组

        // 枚举下边界
        for(int bottom = top; bottom < n; bottom++)
        {
            // 把这一行加进去（压缩列）
            for(int j = 0; j < m; j++)
                sum[j] += a[bottom][j];

            // ⭐ 在 sum 上跑一维 Kadane
            int cur = sum[0], best = sum[0];
            for(int j = 1; j < m; j++)
            {
                cur = max(sum[j], cur + sum[j]);
                best = max(best, cur);
            }

            ans = max(ans, best);
        }
    }
    return ans;
}
int kadane(vector<vector<int>>&a)
{
    int n=a.size();
    vector<vector<int>>lieqianzhui(n+1,vector<int>(n,0));
    vector<vector<int>>hangqianzhui(n,vector<int>(n+1,0));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            hangqianzhui[i][j+1]=hangqianzhui[i][j]+a[i][j];
        }   
    }
    for(int j=0;j<n;j++)
    {
        for(int i=0;i<n;i++)
        {
            lieqianzhui[i+1][j]=lieqianzhui[i][j]+a[i][j];
        }   
    }
    vector<vector<int>>dp(n,vector<int>(n,-10000000));
    vector<vector<vector<int>>>dpx(n,vector<vector<int>>(n));
    vector<vector<vector<int>>>dpy(n,vector<vector<int>>(n));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            int ans1,ans2;
            ans1=ans2=-100000000;
            for(int i1=0;i1<i;i1++)
            {
                dpx[i][j].push_back(((j>0)?max(0, dpx[i][j-1][i1]):0)+lieqianzhui[i+1][j]-lieqianzhui[i1+1][j]);
                ans1=max(ans1,dpx[i][j][i1]);
            }
            for(int j1=0;j1<j;j1++)
            {
                dpy[i][j].push_back(((i>0)?max(0,dpy[i-1][j][j1]):0)+hangqianzhui[i][j+1]-hangqianzhui[i][j1+1]);
                ans2=max(ans2,dpy[i][j][j1]);
            }
            dp[i][j]=max(max(ans1,ans2),a[i][j]);//kadane算法
        }
    }
    int ans=-1000000000;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            ans=max(ans,dp[i][j]);
        }
    }
    return ans;
}
int main()
{
    int n;
    cin>>n;
    vector<vector<int>>a(n,vector<int>(n));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cin>>a[i][j];
        }
    }
    vector<vector<int>>qianzhui(n+1,vector<int>(n+1,0));
    vector<vector<int>>hangqianzhui(n,vector<int>(n+1,0));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            hangqianzhui[i][j+1]=hangqianzhui[i][j]+a[i][j];
            qianzhui[i+1][j+1]=hangqianzhui[i][j+1]+qianzhui[i][j+1];
        }   
    }
    cout<<maxSubmatrix(a);
    return 0;
}