Niuke network: maximum submatrix

 

1. The prefix and

Use a prefix of violence and , This submatrix , We can use the coordinates of the upper left corner and the lower right corner to determine , When we read data , Use an array to store (1,1) It's the upper left corner ,(i,j) Is the sum of the matrix in the lower right corner .

sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+a[i][j]

Then we fix the upper left corner (x,y), Traverse all the lower right corners (i,j)（ Including the upper left corner itself ）, Then the matrix sum of the two can be solved in this way :

sum = sum[i][j]-sum[x-1][j]-sum[i][y-1]+sum[x-1][y-1]

#include<bits/stdc++.h>
using namespace std;
const int N=101;
int sum[N][N];
int n;

void get(int x, int y, int &res){
    for(int i=x;i<=n;++i){
        for(int j=y;j<=n;++j){
            int t=sum[i][j]-sum[x-1][j]-sum[i][y-1]+sum[x-1][y-1];
            if(t>res){
                res=t;
            }
        }
    }
}

int main(){
    cin>>n;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            int t;
            cin>>t;
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+t;
        }
    }
    int res=0x80000001;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            get(i,j,res);
        }
    }
    cout<<res<<endl;
}

2. Dynamic programming && The prefix and

dp The idea is to find the prefix and of each column when reading the data .

Then fix two lines , Ergodic column . The process of traversing a column is a bit like finding the maximum continuous sum of a one-dimensional array . Select the maximum value in the traversal process .

The time complexity here is O(n^3), Compared with the one above O(n^4), Using prefix sum will reduce the complexity of finding the sum of matrices .

#include <bits/stdc++.h>
using namespace std;
const int N=510,inf=1e18;
typedef long long ll;
ll a[N][N],sum[N][N],dp[N];
int main()
{
    ios::sync_with_stdio(false);
    int n;cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
            sum[i][j]=sum[i-1][j]+a[i][j]; //  The first j Before column i Line prefix and 
        }
    }
    ll mx=-inf;
    for(int k1=1;k1<=n;k1++) //  That's ok   Upper end point 
    {
        for(int k2=k1;k2<=n;k2++) //  That's ok   Lower point 
        {
            //dp[0]=0;
            for(int i=1;i<=n;i++) //  Column 
            {
                ll tmp=sum[k2][i]-sum[k1-1][i]; //  The first i Column  [k1,k2] The sum of the trips 
                dp[i]=max(dp[i-1]+tmp,tmp); //  The maximum sub segment sum method 
                mx=max(mx,dp[i]);
            }
        }
    }
    printf("%lld\n",mx);
    return 0;
}