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

Question

I need to know how to find the biggest sum of a given scope in a 2D array, preferably in C to improve the efficiency of the code give below and solve the problem.

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

问题

The great city X is a grid of N rows and M columns. There are given number of people living in each cell. You are asked to position the telecommunication tower so that as many as people are satisfied. The cellular tower can cover a rectangular area of Y rows and X columns. Find the maximum number of people you can satisfy.

约束

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

说明

通过放置覆盖 2x3 区域(由 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 循环。最简单的优化是最大限度地减少范围每次移动的重新计算次数。

我在原始代码中尝试了以下更改:

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

我尝试在 hackerrank.com 上运行该程序，并收到了