Как найти регион, который имеет максимальное количество единиц в C?

Question

У меня есть 2D матрица 500x500, которая содержит значения 0 или 1. Есть ли способ найти высококонцентрированную область, которая содержит значение 1, или, скажем, область с максимальным числом не равным 1? Я пытался обойти всю 2D матрицу с меньшим (Массив размером 50x50), но это занимает очень много времени. Есть ли какой-либо другой способ, который является более эффективным и занимает меньше времени выполнения. Я должен сделать это в программировании на Си.

Answer 1

В комментарии вы заявляете, что вы действительно хотите найти подмассив 50×50, который имеет большинство из них. Наивной реализацией может быть итерация по массиву, а затем по каждому подмассиву для нахождения максимальной суммы:

void subarray(char array[500][500], int *x, int *y, int *pmax)
{
    int i, j, k, l;
    int max = -1;

    for (i = 0; i < 450; i++) {
        for (j = 0; j < 450; j++) {
            int n = 0;

            for (k = 0; k < 50; k++) {
                for (l = 0; l < 50; l++) {
                    n += array[i + k][j + l];
                }
            }

            if (n > max) {
                max = n;
                *x = i;
                *y = j;
                *pmax = max;
            }
        }
    }
}

Это займет много времени, потому что у вас есть четыре вложенных цикла. Лучшим подходом может быть введение вспомогательного массива, в котором хранится число единиц, включая текущую точку для каждой записи в массиве. Эта информация может быть получена постепенно из соседних элементов.

Если вы хотите рассчитать количество единиц в прямоугольнике с верхней левой точкой (x0, y0) и с правой нижней точкой (x1, y1), ты получаешь:

n = count[y1][yy1] + count[y0][x0] - count[y0][x1] - count[y1][x0]

Так:

void subarraye(char array[500][500], int *x, int *y, int *pmax)
{
    int count[500][500];
    int i, j;
    int max = -1;

    count[0][0] = array[0][0];

    for (i = 1; i < 450; i++) {
        count[i][0] = count[i - 1][0] + array[i][0];
    }

    for (i = 1; i < 450; i++) {
        count[0][i] = count[0][i - 1] + array[0][i];
    }

    for (i = 1; i < 500; i++) {
        for (j = 1; j < 500; j++) {
            count[i][j] = count[i - 1][j] + count[i][j - 1]
                        - count[i - 1][j - 1] + array[i][j];
        }
    }       

    for (i = 0; i < 450; i++) {
        for (j = 0; j < 450; j++) {
            int n = count[i + 50][j + 50] + count[i][j]
                  - count[i][j + 50] - count[i + 50][j];

            if (n > max) {
                max = n;
                *x = i + 1;
                *y = j + 1;
                *pmax = n;
            }
        }
    }
}

Индексы отключены на один, потому что количество единиц до исключительной границы (x, y) хранятся в (x - 1, y - 1) и верхний и левый ряд прямоугольников нулевой площади опущены.

Answer 2

Для повышения эффективности вы можете использовать параллельную технику. Вы можете использовать для этого, например, CUDA.

Также неплохо использовать алгоритм конкретного соседа и вычислять наиболее плотное пространство.