a "divide and conquer" algorithm assignment

Question

Now I have N different intergers, I need to find an interval that has the most numbers whose value is between the endpoints of the interval in O(NlogN) time. I call it a "divide and conquer" problem because it is in my final exam's "divide and conquer" category. I have been thinking about it for 2 weeks and have done a lot of experiments, none of them are right(compared to a brute force algorithm). Could someone help me?

examples:

8,1,3,4,7. The answer is 1-7.

2,6,5,4,9,8. The answer is 2-9 or 2-8.

I think the word "interval" doesn't express my meaning. I mean to find a subsequence of the array that has the most numbers whose value is between the endpoints of the subsequence. Eg.1: "1,3,4,7" has two numbers(3,4), and eg.2: both "2,6,5,4,9" and "2,6,5,4,9,8" have three numbers(6,5,4).

here is my code(O(n^2)). @Vaughn Cato I use this to compare to your code.

#! /usr/bin/env python
#coding=utf-8
import itertools
def n2(numbers):
  a = [0]*len(numbers)
  ans = -1
  l = 0
  r = 0
  for j in range(1,len(numbers)):
    t = 0
      for i in range(j-1,-1,-1):
        if numbers[i]<numbers[j]:
          x = t - a[i]
          if x>ans:
            ans = x
            l = i
            r = j
          t += 1
        else:
          a[i] += 1
  return (numbers[l],numbers[r],ans)

def countBetween(numbers,left,right):
  cnt = 0
  for i in range(left+1,right):
    if numbers[left]<numbers[i]<numbers[right]:
      cnt += 1
  return cnt

for numbers in itertools.permutations(range(5)):
  ans1=n2(numbers)
  ans2=longestInterval(numbers)
if(ans1[2]!=ans2[2]):
  print ans1,ans2,numbers

Answer 1

NOTE: This doesn't actually work, but it might give you some ideas.

Think of it this way:

• Let X be the array of numbers.
• Let s be the index of the start of the subsequence.
• Let e be the index of the end of the subsequence.

If you pick an arbitrary partition index p, then the longest subsequence either goes across this partition or it falls to the left or right of that partition. If the longest subsequence goes across this partition, then s < p <= e. To find s, find the index with the most numbers between s and p which are greater than X[s]. To find 'e', find the index with the most numbers between p and e which are less than X[e].

You can recursively check the left and right sides to see if you can find a longer subsequence.

Finding which index has the most greater numbers to the right or the most less than numbers to the left can be done in linear time if you have the indices of X sorted by value:

To find the start index, begin with the first index of your sorted list of indices and say it is the best so far. If the next index is greater than the best so far, then any future index will need to be even farther to the left than our current best to be the new best, so we subtract one from our best index (but remember what the best index really was). If the next index is to the left of our best index, then make it be the best index. Keep repeating this process, for each of the indices in order.

You can do a similar procedure to find the best index for the end on the right side.

The only remaining trick is to maintain the sorted list of indices for whatever range we are working on. This can be done by sorting the entire set of numbers initially and finding their indices, then at each level of the recursion we can split the sorted indices into two sublists in linear time.

Here is a python implementation of the idea:

# Find the index from the given indices that has the most numbers to the
# right of it which are greater in value.  The indices are sorted by
# the value of the numbers at that index. We don't even need to know
# what the numbers are.
def longestLowerSequence(indices):
  best_index=indices[0]
  target_index=best_index
  for i in range(0,len(indices)):
    if indices[i]<target_index:
      best_index=indices[i]
      target_index=best_index
    else:
      target_index-=1
  return best_index

# Find the index from the given indices that has the most numbers to the
# left of it which are less in value.
def longestUpperSequence(indices):
  n=len(indices)
  best_index=indices[n-1]
  target_index=best_index
  for i in range(0,n):
    if indices[n-1-i]>target_index:
      best_index=indices[n-1-i]
      target_index=best_index
    else:
      target_index+=1
  return best_index

# Return the pair of indices which has the most values between it.
def longestRangeFromSortedIndices(numbers,indices,begin,end):
  assert end>begin
  if end-begin<=2:
    return (indices[begin],indices[end-1])
  assert type(indices) is list
  partition=(begin+end)/2
  left_indices=filter(lambda index: index<partition,indices)
  right_indices=filter(lambda index: index>=partition,indices)
  assert len(left_indices)>0
  assert len(right_indices)>0
  left=longestLowerSequence(left_indices)
  right=longestUpperSequence(right_indices)
  left_range=longestRangeFromSortedIndices(numbers,indices,begin,partition)
  right_range=longestRangeFromSortedIndices(numbers,indices,partition,end)
  best_size=countBetween(numbers,left,right)
  best_range=(left,right)
  left_size=countBetween(numbers,left_range[0],left_range[1])
  right_size=countBetween(numbers,right_range[0],right_range[1])
  if left_size>best_size:
    best_size=left_size
    best_range=left_range
  if right_size>best_size:
    best_size=right_size
    best_range=right_range
  return best_range

def sortedIndices(numbers):
  return sorted(range(len(numbers)),key=lambda i: numbers[i])

def longestInterval(numbers):
  indices=sortedIndices(numbers)
  longest_range=longestRangeFromSortedIndices(numbers,indices,0,len(numbers))
  return (numbers[longest_range[0]],numbers[longest_range[1]])

Answer 2

I believe this is a variant of the maximum subarray problem.

It can be solved using divide and conquer as follows:

1. Divide the integer array into equal halves

2. Compute the results R1, R2 on both halves respectively(R1, R2 are lengths of the maximum intervals for each half, and the start and end points are stored as well)

3. Obtain the minimum integer MIN from the first half and the maximum integer MAX from the second half and compute result R3 as the distance from MIN to MAX in the original array (Min and Max are the start and end point respectively)

4. Return the largest of R1, R2 and R3 as the result of the entire problem

Why this works:

The largest interval comes from one of the three cases: 1) the first half 2） the second half 3) across the two halves. Thus, computing the largest of the three yields the optimal result.

Time complexity:

Solving the recurrence:

T(n) = 2T(n/2) + O(n)

gives T(n) = O(nlogn). Note: as the recurrence indicates, we solve two subproblems of half size（2T(n/2)）and find the minimum and maximum integers in two halves in linear time(O(n)).