超短的C++代码（附详细解题思路）

解题思路:①如果按照对每行每列的数字进行逐一分析，很容易就超限，500可不是个小数哦~~~

②那就想怎么能通过加减运算去节省时间，不难想到相邻的行之间相加就可以得到一个子阵，所以，对输入的数据加上前面所有行的数据重新储存到数组中，这里方便区分用两个数组表示a表示储存输入数据的数组，b表示变化后的数组。b0=a0,b1=a0+a1,b2=a0+a1+a2,b3=a0+a1+a2+a3......不难看出b1-b0=a1,b2-b0=a1+a2.....这样就可以得到行上的子阵，再用一个循环去控制列的大小就可以找到每个子阵.

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

int a[550][550],dp[550][550];

int main()

    {

        int n,m,num=-1e5;

        cin>>n>>m;

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

        {

            for(int j=1;j<=m;j++)

            {

            cin>>a[i][j];

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

            dp[i][j]=a[i][j];     //将前面几行的数都储存在数组当中 

            }//dp数组用于动规 

        }

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

     {

        for(int k=0;k<i;k++)

      {

            dp[550][550]={0};

            for(int s=1;s<=m;s++)

        {

        dp[k][s]=max((a[i][s]-a[k][s]),(a[i][s]-a[k][s]+dp[k][s-1]));

        num=max(dp[k][s],num);

        } 

    }

    }

    cout<<num;

    return 0;

}