如何在二维数组中找到给定范围的最大总和？

Question

我需要知道如何在二维数组中找到给定范围的最大总和，最好在C中以提高下面给出的代码的效率并解决问题。

要更好地理解这一点，请阅读下面我需要解决的问题。

问题

伟大城市X是N行M列的网格。在每个细胞中有多少人被给予 。你被要求定位 电信塔，以便让人满意。蜂窝塔可以覆盖Y行和X列的矩形区域。 找到您可以满足的最大人数。由元胞塔覆盖

约束

1 <= N, M <= 1000 
1 <= Y <= N, 1 <= X <= M 
1 <= number of people in a cell <= 1000 

矩形区域不应该覆盖任何细胞部分。

输入

输入的第一行包含4个位数N，M，Y和X分别用空格分开。接下来的N行中包含第1行到第N行的整数。每行将M个整数给出生活在每个单元中的人数由空格分隔。

输出

输出应该只包含一个整数的人，你能满足的最大数量。

采样输入

4 5 2 3 
3 1 1 1 2 
2 5 6 7 1 
1 2 9 9 1 
1 1 1 1 1 

样本输出

38 

说明

通过放置覆盖2×3区域的塔，可以满足最多的人数，该区域由5,6,7,2,9和9个单元组成。

5 + 6 + 7 + 2 + 9 + 9 = 38 

我的代码

#include <stdio.h> 
#include <string.h> 
#include <math.h> 
#include <stdlib.h> 

int main() { 

int N, M, Y, X; 
scanf("%d %d %d %d", &N, &M, &Y, &X); 

int max = 0; 
int total = 0; 

int data[N][M]; 

for(int i = 0; i < N; i++) 
    for(int j = 0; j < M; j++) 
     scanf("%d",&(data[i][j]));  

for(int i = 0; i < N; i++) 
{ 
    for(int j = 0; j < M; j++) 
    { 
     total = 0; 

      for(int l = 0; (l < Y) && (i + Y) <= N; l++) 
      { 

       for(int k = 0; (k < X) && (j + X <= M); k++) 
       { 
        total += data[i+l][j+k]; 
       } 

       if(total > max) 
        max = total;      
     } 
    } 
} 

printf("%d",max); 
return 0; 
} 

此代码失败，因为它太线，并采取了很多的时间在使用较大的输入。

你可以尝试一下自己的问题，here

Answer 1

我想主要的问题在你的电话号码并网问题的解决嵌套for循环。最简单的优化是最小化范围内每次移动的重新计算次数。

我tryed在原来代码中的以下变化：

#include <stdio.h> 
#include <string.h> 
#include <math.h> 
#include <stdlib.h> 

int main() { 

    int N, M, Y, X; 
    scanf("%d %d %d %d", &N, &M, &Y, &X); 

    int max = 0; 
    int total = 0; 

    int data[N][M]; 

    for(int i = 0; i < N; i++) 
     for(int j = 0; j < M; j++) 
      scanf("%d",&(data[i][j])); 
    //////////////////////////////////////////////////////////// 
    // calculation of the first total and initial max 
    int startTotal = 0; 
    int r, c; 
    for(r = 0; r < Y-1; r++) 
    { 
     for(c = 0; c < X-1; c++) 
     { 
      startTotal += data[r][c]; 
     } 
    } 
    max = startTotal; 

    for(int i = 0; i+Y <= N; i++) 
    { 
     // add next line 
     for(int c = 0; c < X-1; c++) 
     { 
      startTotal += data[i+Y-1][c]; 
     } 
     total = startTotal; 
     for(int j = 0; j+X <= M; j++) 
     { 
      // add next column 
      for(int r = i; r < i+Y; r++) 
       total += data[r][j+X-1]; 
      // compare 
      if(total > max) 
      { 
       max = total; 
      } 
      // subtract the first column 
      for(int r = i; r < i+Y; r++) 
       total -= data[r][j]; 
     } 
     // subtract the first line 
     for(int c = 0; c < X-1; c++) 
     { 
      startTotal -= data[i][c]; 
     } 
    } 
    //////////////////////////////////////////////////////// 
    printf("%d",max); 
    return 0; 
} 

我已经tryed运行在hackerrank.com程序，并获得