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.
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 &amp; \text{if }a_{i+1}-a_i &gt;k\\ 1 + g(i)&amp;\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)$.