寻找一个二维数组中连续的一行，其中包含最多的1。

Question

我有一个大小为m*m的二维数组，元素值为0或1。此外，该数组的每一列都有一个连续的1块（其余为0）。该数组本身太大，无法存储在内存中（多达10^6行），但对于每一列，我可以确定该列中1的下限a和上限b。对于给定的n，我需要找出具有最大数量1的n个连续行。我可以通过逐行计算总和并选择总和最大的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行，总共13个1。 (第2行到第4行也可以最大化总和，因为有一个平局。)

- abcdf ndjdnkn

---

最大数量的1是什么意思？您能否提供一个较小的示例，以便我们可以看到它？ - Unome

那么 n 是一个输入参数，满足 n <= m？ - John Coleman

无法避免计算每行的总和。由于您必须从某个地方读取输入，因此可以在读取时计算总和，并将结果存储在大小为“m”的一维数组中。至于其余部分，请发布您已经尝试过的代码，并提供输入和输出的示例。 - user3386109

你可以轻松地计算出前i列中哪些行具有最大数量的1，当你从0迭代到结尾时，你会发现一些行没有希望赶上当前的最大值。最坏情况（所有地方都是1或0）不会改善。最好的情况下你可以把时间减半。 - user3528438

鉴于您最近的编辑 - 我没有看到您从harr中确定answer的方式存在任何低效性。这在行数上是线性的，即使有100万行（而不是您代码示例中的10000行），该计算部分也将在几秒钟内运行。我怀疑在加载harr时不断更新临时的answer是否会产生反作用。您确定read_int()不是瓶颈吗？ - John Coleman

Answer 1

以下是不同的方法。将每对a，b视为定义形式为[a，b + 1）的区间。任务是找到最大化该区间中数字的括号深度之和的n个连续索引。每个新的a将在a处增加括号深度1。每个新的b会导致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的循环合并。 我将其保留为两次遍历，以更好地说明如何从括号差异中获取最终harr值的逻辑。）

（当编译并运行此代码时，输出如下：）

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

- John Coleman

---

这就是我已经实现的，但我需要对10^6行执行此操作，这将耗费太多时间。 - abcdf ndjdnkn

如果您有一个非稀疏矩阵（4 TB？），我不认为您能做得更好。如果它是稀疏的 - 您如何表示数据？ - John Coleman

@John Coleman，a和b是什么？这是一个无法编写程序的人可怕的代码。 - Vlad from Moscow

@John Coleman 问题在于你的答案会被其他人阅读，他们应该能够理解你展示的代码。 - Vlad from Moscow

@VladfromMoscow 您无疑是正确的。另一方面，根据问题的上下文解释答案是很常见的。如果您愿意，您可以指责 OP 没有包含一个自包含的程序，但是批评我首先理解他们的问题，然后通过展示如何修改他们实际提供的代码片段来回答他们的问题似乎有些奇怪。不过，您确实有一个好观点。我将编辑我的问题，提供 read_int() 的样本定义（似乎依赖于某些全局状态）和一个 main 函数。 - John Coleman

Answer 2

我不确定以下内容在您的10^6行中如何扩展，但它可以在单个传递中管理x连续行的尾部总和，而无需调用函数。 这可能值得一试。还要确保使用全优化编译，以便编译器也可以发挥作用。

我的最初想法是找到某种方法来读取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

- David C. Rankin