給定兩個數組數組

Question

給定數字a [1]，...，a [n]和b [1]，...，b [n]，其中每個數字爲0或1，算法，它採用Θ（n）時間和空間來找出最大跨度（i，j），使得a [i] + a [i + 1] + ... a [j] = b [i] + b [ i + 1] + ..... b [j]或者報告沒有這樣的跨度。

我遇到了這個計劃：

#include <stdio.h> 
    #define size 100 //assume n is less than 100 
    int main() 
    { 
    int n, a[size], b[size]; 
    int start[2*size], end[2*size]; 
    int sum1 = 0, sum2 = 0, i; 
    int diff[size]; 
    printf("Enter n: "); 
    scanf("%d", &n); 
    for(i = 0; i < n; i++) 
    { 
     printf("Enter a[%d]: ", i); 
     scanf("%d", &a[i]); 
    } 
    for(i = 0; i < n; i++) 
    { 
     printf("Enter b[%d]: ", i); 
     scanf("%d", &b[i]); 
    } 

    for(i = 0; i < n; i++) 
    { 
     if(a[i]) sum1++; 
     if(b[i]) sum2++; 
     diff[i] = sum1 - sum2; 
    } 
    for(i = 0; i < 2*n; i++) 
     start[i] = -1; 
    start[n] = end[n] = 0; //initially sum is 0 at the beginning of array and the first n-1 elements of start and end are used if sum of A till ith element is less than sum of B till ith element 
    for(i=0; i < n; i++) 
    { 
     if(start[diff[i] + n] == -1) 
      start[diff[i] + n] = i; 
     end[diff[i] + n] = i; 
    } 
    int max = -1; 
    int savei = -1; //savei is for storing the sum having the largest span 

    for(i = 0; i < 2*n; i++) 
    { 
     if(start[i] > -1 && (end[i] - start[i] > max)) 
     { 
      max = end[i] - start[i]; 
      savei = i; 
     } 

    } 
    if(savei >= 0) 
    { 
     printf("The largest span is from %d to %d\n", start[savei]+(savei != n), end[savei]); 
    //when sum zero is having the largest span, span starts from first element itself. Else, the span starts from the next element from which the span does not change 
    } 
    else 
    { 
     printf("No span\n"); 
    } 
} 

我無法理解這個算法是如何工作的。請幫我理解這一點。

據我所知，該程序到目前爲止計算了a的總和與b的總和之間的差值。我們將Start初始化爲-1，並將start [n]和end [n]設置爲0.之後，我不知道程序爲什麼會這樣做。

Answer 1

這是主意。

Define pre_a[i] = a[0]+a[1]+...+a[i] and pre_b[i] = b[0]+b[1]+...+b[i]。

我們什麼時候有a[i]+a[i+1]+...+a[j] = b[i]+b[i+1]+...+b[j]？ 當pre_a[j]-pre_a[i-1]=pre_b[j]-pre_b[i-1]或等效pre_a[j]-pre_b[j]=pre_a[i-1]-pre_b[i-1]時，我們有這個。

如果我們現在定義diff[i] = pre_a[i]-pre_b[i]我們可以看到我們的問題實際上發現j>i，使得diff[j] == diff[i-1]和j-i是最大的。由於diff[i]範圍超過[-n,n]然後在[-n,n]每個k我們可以計算出其最大j使得diff[j]=k和這是最小j使得diff[i]=k（分別存儲在end和start）。剩下要做的就是爲-n<=k<=n找到最大end[k]-start[k]。