0
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Apr 11, 2021 at 20:48

1 Answer 1

1
$\begingroup$

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)$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.