Implement simple algorithm using divide and conquer

Question

I am trying to implement the following algorithm using the divide and conquer method in order to get the running time to O(n*logn).

Given a sequence of numbers a_1, a_2,…, a_n and a number k, find i and j such that 1<= j – i <= k while maximizing a_i + a_j.

For example for the sequence 10,2,0,8,1,7,1,0,11 and k = 2, the maximum value is 15 = 8 + 7.

I have implemented some sort of divide and conquer method, but I'm struggling to figure out how to check values that go across each of the divide intervals. Here is what I have so far:

int MaxInterval(int array[], int left, int right, int k)
{
    int BestSum = 0;
    int sumL = 0;
    int sum = 0;
    int sumR = 0;
    int sumMid = 0;
    int count = 0;
    if( right - left <= 2*k-3 ) //
    {
      //elaborate straightforward search right way
      for(int i = left; i <= right; i++)
      {
          sum = 0;
          count = k;
          for(int j = i+1; j <= right; j++ )
          {
              if(count == 0) break;
              sum = array[i] + array [j];
              if(sum > BestSum) BestSum = sum;
              count--;
          }

      }
      return BestSum;
    }
    int mid = (right + left)/2;
    sumL = MaxInterval(array, left, mid, k);
    sumR = MaxInterval(array, mid + 1, right, k);
    sumMid = MaxInterval(array, max(left, mid - k + 2), min(right, mid + k - 1), k);
    return max(max(sumL, sumR), sumMid);
}

I think I am on some-what of the right track, I'm just struggling to figure out how to incorporate check sums of numbers that go across two of the intervals, without using a brute-force method which would yield O(n^2) complexity.

If there are any pointers or tips on how I can continue this, it would be greatly appreciated. Also, I am currently working under the assumption that there is an even number of integers in the array. Thanks guys.

This problem might be solved in O(N) time, if space complexity O(k) is allowed. Look at home.tiac.net/~cri/2001/slidingmin.html (and there are some topics on sliding window minimum at StackOverflow) — MBo
– MBo, Commented May 21, 2012 at 4:17
Thanks for the heads up. I still would like to implement this using a divide-and-conquer method, just to see how it it would work. — Tesla
– Tesla, Commented May 21, 2012 at 4:33

MBo · Accepted Answer · 2012-05-21 18:36:54Z

1

Some clues in pseudocode. Example for n=8, k = 2 - this code will search the best result from a[0..3], a[4..7] and a[2..5]. Notice that I've removed additional arrays.

int MaxInterval(int array[], int left, int right, int k)
{
    if( right - left <= 2*k-1 ) //
    {
      //elaborate straightforward search right way
      return BestSum;
    }
    sumL = MaxInterval(array, left, mid, k);
    sumR = MaxInterval(array, mid + 1, right, k);
    sumMid = MaxInterval(array, max(left, mid - k + 1), min(right, mid + k), k);
    return max(sumL, sumR, sumMid);
}

edited May 21, 2012 at 18:36

answered May 21, 2012 at 4:59

MBo

80.7k5 gold badges61 silver badges99 bronze badges

Sign up to request clarification or add additional context in comments.

12 Comments

Tesla Over a year ago

In the if statement, shouldn't it be just "right - left < 2*k - 3" as opposed to the "<=". Since k=3, checking a[0..3] would be checking 4 elements, as opposed to the max of k?

MBo Over a year ago

We should check k-1 elements left to border, and k-1 elements right to border. 2k-2 elements occupy range [l..l+2*k-3]. For k=3 we need to check 4 elements

Tesla Over a year ago

Oh okay, I see now. So a simple, almost brute-force, check just needs to be implemented? Something ala start from left, sum k elements to the right, go to left+1, sum k elements to the right, etc. all the while comparing the sums?

MBo Over a year ago

Why do you say about (and use in you code) sum of k elements? As I understand, the task is to find pair of elements with max sum and limited distance

Tesla Over a year ago

Oh wow, I completely misread that. I was working on a similar algorithm for something else that used k elements, and I got confused. I updated the function to what I have now. I believe it is close, but I'm not there yet. I seem to have with sumMid division when k=2, for example.

|

Collectives™ on Stack Overflow

Implement simple algorithm using divide and conquer

1 Answer 1

12 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

12 Comments

Your Answer

Sign up or log in

Post as a guest

Related