Monday, September 10, 2012

Find longest interval with maximum sum

We are given with two arrays A and B. Each of size N. Elements of array contains either 1 or 0. We have to find such an interval (p,q)(inclusive) such that the sum of all the elements of A (between this interval) and sum of all elements of B (between this interval ) is equal. i.e.
a[p]+a[p+1]....+a[q]= b[p]+b[p+1]....+b[q]

Solution:

a)Calculate the prefix sum of both the arrays รข€“ value at each index represents the sum till that index
  void prefixSum(int *array, int *sum)
{
     int i;
     for(i=0;i < N;i++)
     { 
             if(i==0) 
             {
                sum[i]=array[i];
             }
             else
             {
                 sum[i]=array[i]+sum[i-1];
             }
     }
}
b)Make 4 variables:
size: to keep track of largest subset size found till now sum: sum of that subset
p: starting index of the subset
q: ending index of the subset
Initially search of there is any sub set from starting index in both the arrays that has the same sum, if found update the value of size, sum and indices p, q.
for(int i=0;i < N;i  )
    {
            if(sumA[i]==sumB[i])
            {
                          if((i 1) > size)
                          {
                                        size=i 1;
                                        p=0;
                                        q=i;
                                        sum=sumA[i];
                          }
            }
    }
c)Now search for largest subset by incrementing the starting position and continue this loop till the size of the array.
for(int i=0;i < N-1;i  )
    {
            for(int j=i 1;j < N;j  )
            {
                    if( (sumA[j]-sumA[i]) == (sumB[j]-sumB[i]) )
                    {
                          if( (j-i) > size )
                          {
                              size= j-i;
                              p=i 1;
                              q=j;
                              sum=sumA[j]-sumA[i];
                          }
                          else if( (j-i) == size )
                          {
                               if( (sumA[j]-sumA[i]) > sum )
                                   sum=(sumA[j]-sumA[i]);
                          }
                          else {}

                    }
            }
    }
Time complexity of the algorithm in O(N2) because of the double loop of i and j

No comments:

Post a Comment