查找具有最大数量 1 的二维数组的连续行

Question

我有一个大小为 m*m 的二维数组，元素值为 0 或 1。此外，数组的每一列都有一个连续的 1 块（该块外有 0）。数组本身太大，无法保存在内存中（多达 10^6 行），但对于每一列，我可以确定下限 a 和上限 b，该列中的 1。对于给定的 n，我需要找出那些 n 具有最大数量 1 的连续行。对于较小的数字，我可以通过逐行计算总和，然后选择总和最大的 n 连续行来轻松地做到这一点，但对于大数字，它会消耗太多时间。有什么有效的方法可以计算这个吗？也许使用动态规划？

这是一个示例代码片段，显示了我当前的方法，其中对 read_int() 的连续调用（此处未给出）提供连续列的下限和上限：

   long int harr[10000]={0};       //initialized to zero
   for(int i=0;i<m;i++)
    {
        a=read_int();
        b=read_int();
        for(int j=a;j<=b;j++)        // for finding sum of each row
           harr[j]++;
    }
   answer=0;
    for(int i=0;i<n;i++)
    {
        answer=answer+harr[i];
    }
    current=answer;
    for(int i=n;i<m;i++)
    {
        current=current+harr[i]-harr[i-n];
        if(current>answer)
        {
            answer=current;
        }
    }

例如（m = 6 且 n = 3）

这里的答案是第 1 行到第 3 行，这些行中的 1-count 总数为 13。（第 2 行到第 4 行也使总和最大化，因为存在平局。）

Answer 1

这是一种不同的方法。将每对 a、b 视为定义 [a,b+1) 形式的区间。任务是找到 n 个连续索引，使该区间内数字的 括号深度 的总和最大化。每个新的 a 都会将 a 处的括号深度增加 1。每个新的 b 都会导致括号深度 after b 去下降 1。在第一遍中——只需加载这些括号深度增量。然后一次通过从这些增量中获取括号深度。下面的代码说明了这种方法。出于测试目的，我将 m 减少到 6，并通过访问硬连线数组（对应于问题中的示例）替换了对未知 read_int() 的调用：

#include <stdio.h>

int main(void){
    int a,b,answer,current,lower,upper;
    int n = 3;
    int lower_bound[6] = {0,1,2,3,1,2};
    int upper_bound[6] = {3,4,3,5,2,4};
    int m = 6;
    int harr[6]={0};

    //load parenthesis depth-deltas (all initially 0)
       for(int i=0;i<m;i++)
        {
            a = lower_bound[i];
            b = upper_bound[i];
            harr[a]++;
            if(b < m-1)harr[b+1]--;
        }

    //determine p-depth at each point
        for(int i = 1; i < m; i++){
            harr[i] += harr[i-1];
        }

    //find optimal n-rows by sliding-window
       answer = 0;
        for(int i=0;i<n;i++)
        {
            answer = answer+harr[i];
        }
        current  =answer;
        lower = 0;
        upper = n-1;

        for(int i=n;i<m;i++)
        {
            current = current+harr[i]-harr[i-n];
            if(current>answer)
            {
                answer = current;
                lower = i-n+1;
                upper = i;
            }
        }
    printf("Max %d rows are %d to %d with a total sum of %d ones\n", n,lower,upper,answer);
    return 0;
}

（显然，加载 harr 的循环可以与计算 answer 的循环结合使用。我将其保留为两次传递以更好地说明最终 [=21= 的逻辑] 值可以从括号deltas中获得）。

编译此代码时运行其输出为：

Max 3 rows are 1 to 3 with a total sum of 13 ones

Answer 2

我不确定以下内容将如何针对您的 10^6 行进行缩放，但它在没有函数调用开销的情况下在单次传递中管理 x 连续行的尾部总和。可能值得一试。还要确保您正在使用完全优化进行编译，以便编译器也可以添加它的 2 美分。

我最初的想法是找到一些方法来读取 x * n 整数（从您的 m x n 矩阵）并以某种方式查看其上的一组设置位字节数。（检查字节序）并获取每个整数的第一个或最后一个字节以检查是否设置了位。然而，该逻辑似乎与简单地携带尾随 x 行的总和并在尝试优化逻辑时逐步遍历数组一样昂贵。

你的数据中没有任何基准可供比较，但也许这会给你另外一两个想法。:

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

#ifndef CHAR_BIT
#define CHAR_BIT  8
#endif

#ifndef INT_MIN
#define INT_MIN -(1U << (sizeof (int) * CHAR_BIT - 1))
#endif

int main (int argc, char **argv) {

    /* number of consecutive rows to sum */
    size_t ncr = argc > 1 ? (size_t)atoi (argv[1]) : 3;

    /* static array to test summing and row id logic, not
       intended to simulate the 0's or 1's */
    int a[][5] = {{1,2,3,4,5},
                  {2,3,4,5,6},
                  {3,4,5,6,7},
                  {4,5,6,7,8},
                  {3,4,5,6,7},
                  {0,1,2,3,4},
                  {1,2,3,4,5}};
    int sum[ncr];               /* array holding sum on ncr rows */
    int sumn = 0;               /* sum of array values */
    int max = INT_MIN;          /* variable holding maximum sum  */
    size_t m, n, i, j, k, row = 0, sidx;

    m = sizeof  a / sizeof *a;  /* matrix m x n dimensions */
    n = sizeof *a / sizeof **a;

    for (k = 0; k < ncr; k++)   /* initialize vla values */
        sum[k] = 0;

    for (i = 0; i < m; i++)     /* for each row */
    {
        sidx = i % ncr;         /* index for sum array */

        if (i > ncr - 1) {      /* sum for ncr prior rows */
            for (k = 0; k < ncr; k++)
                sumn += sum[k];
            /* note 'row' index assignment below is 1 greater
               than actual but simplifies output loop indexes */
            max = sumn > max ? row = i, sumn : max;
            sum[sidx] = sumn = 0; /* zero index to be replaced and sumn */
        }

        for (j = 0; j < n; j++) /* compute sum for current row */
            sum [sidx] += a[i][j];
    }

    /* output results */
    printf ("\n The maximum sum for %zu consecutive rows: %d\n\n", ncr, max);

    for (i = row - ncr; i < row; i++) {
        printf (" row[%zu] : ", i);
        for (j = 0; j < n; j++)
            printf (" %d", a[i][j]);
        printf ("\n");
    }

    return 0;
}

示例输出

$./bin/arraymaxn

 The maximum sum for 3 consecutive rows: 80

 row[2] :  3 4 5 6 7
 row[3] :  4 5 6 7 8
 row[4] :  3 4 5 6 7

$./bin/arraymaxn 4

 The maximum sum for 4 consecutive rows: 100

 row[1] :  2 3 4 5 6
 row[2] :  3 4 5 6 7
 row[3] :  4 5 6 7 8
 row[4] :  3 4 5 6 7

$ ./bin/arraymaxn 2

 The maximum sum for 2 consecutive rows: 55

 row[2] :  3 4 5 6 7
 row[3] :  4 5 6 7 8

注：如果有多个等价的最大连续行（即两组1加起来相同的行），选择第一个出现最大值的行.

我不确定您选择使用哪些优化进行编译，但无论您使用哪种代码，您始终可以尝试向编译器提供简单提示以内联所有函数（如果您的代码中有函数）和全面优化代码。两个有用的是：

gcc -finline-functions -Ofast

查找具有最大数量 1 的二维数组的连续行

Find consecutive rows of a 2D array with maximum number of 1s

c

arrays

dynamic-programming