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

Question

我有一个大小为 m*m 的二维数组，元素值为 0 或 1。此外，数组的每一列都有一个连续的 1 block (该 block 外有 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 的循环结合使用。我将其保留为两次以更好地说明最终的逻辑harr 值可以从括号中的增量中获得)。

编译并运行此代码时，其输出为:

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