Minimum sub-vector size k with the divide and conquer technique

Question

Good morning, I have problems to solve:

You have a vector of size n, you want to find a sub-vector of size m and that the sum of its elements is minimal

An example of how this works is: see example of operation where the minimum sub-vector is: {1,3,1} with sum 5

I need to analyze this problem both by brute force (sliding windows explained below), and by the technique of divide and conquer. Then I will write a comparative report and explain that with sliding windows it works much better. This paper is for a university project on algorithm comparison. But I need to build it explicitly with D&C.

I have it done as follows, but I have problems with base cases and returning the minimum sum sub-vector.

// Function to find the minimum between two numbers
int min(int a, int b) { return (a < b)? a : b; }

// Function to find the minimum between three numbers
int min(int a, int b, int c) { return min(min(a, b), c); }

// Function to find the minimum sum that passes through the center of the vector
int minSumCenter(int v[], int l, int center, int h)
{

    // Elements to the left of the center
    int sum = 0;
    int left_sum = INT_MAX;
    for (int i = center; i >= l; i--)
    {
        sum = sum + v[i];
        if (sum < left_sum)
          left_sum = sum;
    }

    // Elements to the right of centre
    sum = 0;
    int right_sum = INT_MAX;
    for (int i = center+1; i <= h; i++)
    {
        sum = sum + v[i];
        if (sum < right_sum)
          right_sum = sum;
    }

    // Return de los elementos que están tanto a la izquierda como a la derecha
    return left_sum + right_sum;
}

// Minimum sum sub-vector size m, size v is h-l
int subvectorMinDyV(int v[], int l, int h, int m){
   // Base Case 1
   if ((h-l) <= m) {
       int sum = 0;
       for(int i=0; i<m; i++)
        sum += v[i];
       return sum;
  // Base Case 2
}else if(m*2-1 <= (h-l)){
       int sum=0;
       int sumMin = INT_MAX;
       for(int i=0; i<(l+h)-m;i++){
           sum=0;
           for(int j=i; j<m; j++)
            sum += v[j];

           if(sum < sumMin)
            sumMin = sum;
       }
       return sumMin;
   }


   int center = (l + h)/2;
   /* Possible cases
      a) minimum sum sub-vector is on the left
      b) minimum sum sub-vector is on the right
      c) minimum sum sub-vector is a in the middle */
   return min(subvectorMinDyV(v, l, center, m),
              subvectorMinDyV(v, center+1, h, m),
              minSumCenter(v, l, center, h));
}

int main(){
   int v[] = {6,10,4,2,14,1};
   int n = sizeof(v)/sizeof(v[0]);
   int sumMin = subvectorMinDyV(v, 0, n-1, 3);
   cout << "The minimum amount with DyV is: " << sumMin << endl;

   return 0;
}

Thank you very much.

Answer 1

I'm not sure what you mean by divide-and-conquer exactly. The sliding window approach, as pointed out by others, is O(n). (You can't do any better, since you need to look at every element at least once.)

The solution you have is close, except that you are recomputing the sums needlessly. This should do the job

void subvectorMin(int* v, int n, int m)
{
  if (n < m)
  {            
    std::cout << "Cannot calculate sub-vector m. (m<n)";
    return; // return early
  }

  // compute the sum of first m elements
  int sum = 0;  
  for(int i = 0; i < m; ++i) 
    sum += v[i];

  // assume answer is at position 0
  int pos = 0;
  int min_sum = sum;

  // check if there is a minimum sum somewhere else
  for(int i = m; i < n; ++i)
  {
    sum = sum + v[i] - v[i - m]; // THIS is the sliding window that 
                                 // avoids the sum being recomputed

    // if smaller sum is found, update the position
    if(sum < min_sum)
    { 
        min_sum = sum; 
        pos = i - m + 1;
    }
  }    

  std::cout << "The minimum component sum is: " << min_sum
            << " , subvector: {";
  for(int i = pos; i < pos + m; ++i)
      std::cout << " " << v[i];
  std::cout << " }" <<std::endl;
}