如何在二維數組中找到給定範圍的最大總和？

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程序，並獲得