# Divide and conquer problem:sequence of integers (with possible repetitions)

I was trying to solve this problem.

Let $$A[1] . . . , A[n]$$ an ordered sequence of integers (with possible repetitions) and let $$k$$ be any integer. A contiguous subsequence $$A[i], A[i + 1], . . . A[j]$$ of $$A$$ is $$k$$-separated if the difference between every pair of its consecutive elements is at most $$k$$.

For example, if $$A = [1, 3, 3, 4, 4, 4, 5, 7, 8]$$, then the contiguous subsequence $$3, 3, 4, 4, 4, 5$$ is $$1$$-separated but not $$0$$-separated.

We would like an algorithm that given $$A$$ and $$k$$ as input returns the length of the longest contiguous k-separated subsequence.

Some examples:

• Input: $$A = [1, 3, 3, \textbf{4, 4, 4}, 5, 7, 8]$$, $$k = 0$$. Output: $$3$$ (longest contiguous $$0$$-separated subsequence has been hightligthed)
• Input: $$A = [1, \textbf{3, 3, 4, 4, 4, 5}, 7, 8]$$, $$k = 1$$. Output: $$6$$ (longest contiguous $$1$$-separated subsequence has been hightligthed)

This can be solved in $$O(n^2)$$ with a nested loop that checks all possible contiguous subsequences but we would like to do better.

I understand that I need to split my array in 2, but after that I don't know how to find the condition to select first half or second. How will be the algorithm to find the correct answer? Any help it's welcome.

• Please don't delete your question after receiving a question. Part of our mission is to build up an archive of high-quality questions and answers, that will be useful to others as well.
– D.W.
Apr 11, 2021 at 20:48

If you want to use a divide-and-conquer algorithm, you can cut the array $$A = [a_1, …, a_n]$$ in two arrays by the middle $$B = [a_1, …, a_{\frac{n}{2}}]$$ and $$C = [a_{\frac{n}{2}+1}, …, a_n]$$.

Then the longest $$k$$-separated sequence in $$A$$ is one of the three following:

• the longest $$k$$-separated sequence in $$B$$;
• the longest $$k$$-separated sequence in $$C$$;
• the concatenation of the longest $$k$$-separated sequence in $$B$$ ending with $$a_{\frac{n}{2}}$$ with the longest $$k$$-separated sequence in $$C$$ beginning with $$a_{\frac{n}{2}+1}$$, with the condition $$a_{\frac{n}{2}+1} - a_{\frac{n}{2}} \leq k$$.

Now the first two values can be computed recursively, and the third can be computed easily in time complexity $$O(n)$$. The complexity of this algorithm verifies $$C(n) = 2C\left(\frac{n}{2}\right) + O(n)$$, which implies $$C(n) = O(n\log n)$$.

Without divide-and-conquer, I think there exists a $$O(n)$$ dynamic programming algorithm:

For $$A = [a_1, …, a_n]$$ and $$i \in [\![1, n]\!]$$, define:

• $$f(i)$$: length of the longest $$k$$-separated sequence in $$[a_1, …, a_i]$$;
• $$g(i)$$: length of the longest $$k$$-separated sequence in $$[a_1, …, a_i]$$ ending with $$a_i$$.

Then it is easy to see that:

• $$g(i + 1) = \left\{\begin{array}{rl}1 & \text{if }a_{i+1}-a_i >k\\ 1 + g(i)&\text{otherwise}\end{array}\right.$$
• $$f(i + 1) = \max(f(i), g(i + 1))$$

That way, you can easily compute $$f(n)$$, which is the value you want, in time complexity $$O(n)$$.

• Please write a complete question, I cannot understand what you are trying to ask. Apr 9, 2021 at 14:03
• I wrote the algorithm in english, you need to figure out the details by yourself, otherwise you will not make any progress. Apr 9, 2021 at 14:18
• I'm sure you can find it yourself! Apr 9, 2021 at 14:26