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;
}