NYOJ - 104 最大和【DP】

解题思路：

这个就是二维的最大连续和问题。

我们可以通过转化为一维的最大连续和来求解，方法就是用一个辅助数组temp。temp的作用就是将n行的矩阵压缩为一行（累加求和），这样就转化为了一维的最大连续和问题。

然后我们对从第i行开始的子矩阵进行枚举即可。复杂度为O（N*N)

代码如下：

[cpp]
#include<iostream>
#include<cstdio>
#include<climits>
#include<cstring>
using namespace std;

const int N = 110;
int row, col;
int matrix[N][N];
int temp[N][N];     //辅助数组

void DP(void)
{
    int thissum, maxsum;
    maxsum = INT_MIN;

    for(int i = 1; i <= row; ++i)        //累加求和
        for(int j = 1; j <= col; ++j)
            temp[i][j] = temp[i - 1][j] + matrix[i][j];

    for(int i = 1; i <= row; ++i)
        for(int j = i; j <= row; ++j)    //枚举子矩阵
        {
            thissum = 0;
            for(int k = 1; k <= col; ++k)
            {
                if(thissum > 0)
                    thissum += temp[j][k] - temp[i - 1][k];
                else
                    thissum = temp[j][k] - temp[i - 1][k];

                maxsum = max(maxsum, thissum);
            }
        }
    printf("%d\n", maxsum);
}

int main(void)
{
    int ncase;
    scanf("%d", &ncase);
    while(ncase--)
    {
        memset(temp, 0, sizeof(temp));
        scanf("%d %d", &row, &col);

        for(int i = 1; i <= row; ++i)
            for(int j = 1; j <= col; ++j)
                scanf("%d", &matrix[i][j]);

        DP();
    }
    return 0;
}

#include<iostream>
#include<cstdio>
#include<climits>
#include<cstring>
using namespace std;

const int N = 110;
int row, col;
int matrix[N][N];
int temp[N][N]; //辅助数组

void DP(void)
{
int thissum, maxsum;
maxsum = INT_MIN;

for(int i = 1; i <= row; ++i)  //累加求和
  for(int j = 1; j <= col; ++j)
   temp[i][j] = temp[i - 1][j] + matrix[i][j];

for(int i = 1; i <= row; ++i)
  for(int j = i; j <= row; ++j) //枚举子矩阵
  {
   thissum = 0;
   for(int k = 1; k <= col; ++k)
   {
    if(thissum > 0)
     thissum += temp[j][k] - temp[i - 1][k];
    else
     thissum = temp[j][k] - temp[i - 1][k];

    maxsum = max(maxsum, thissum);
   }
  }
printf("%d\n", maxsum);
}

int main(void)
{
int ncase;
scanf("%d", &ncase);
while(ncase--)
{
memset(temp, 0, sizeof(temp));
scanf("%d %d", &row, &col);

  for(int i = 1; i <= row; ++i)
   for(int j = 1; j <= col; ++j)
    scanf("%d", &matrix[i][j]);

DP();
}
return 0;
}

补充：软件开发 , C++ ,