Here's my thought.

Consider DP. We define $$$dp[i]$$$ as the minimal maximum distance of the two cars if one car is at position $$$i$$$ and the other is at some position before $$$i$$$.

Our goal is to calculate $$$dp[n]$$$ and this is the answer. We calculate $$$dp[1]$$$ to $$$dp[n]$$$ one by one.

Let the $$$i$$$-th position is $$$p[i]$$$. Now we have the transfer $$$dp[i] = \min_{j=1}^{i-1}\max(dp[j], \max_{k=j+1}^{i}(|p[j]-p[k]|))$$$, and don't forget to transfer from the initial positions just like this.

We can easily gat $$$\max_{k=j+1}^{i}(|p[j]-p[k]|) = \max(|\max_{k=j+1}^{i}(p[k])-p[j]|, |\min_{k=j+1}^{i}(p[k])-p[j]|)$$$ with some data structure in $$$O(1)$$$.

Using brute force on $$$j$$$ will obviously get TL so we should use faster algorithm. Consider binary search. You can find that when $$$j$$$ is increasing, $$$dp[j]$$$ is non-decreasing and $$$\max_{k=j+1}^{i}(|p[j]-p[k]|)$$$ is non-increasing. So binary search will work.

The total time complexity is $$$O(n\log_2n)$$$.

The previous solution is wrong. Solution below is the correct one, and my code got AC.

We should maintain a set of positions during DP.

First, we should do binary search on the answer. So we should ensure that for a given distance $$$m$$$, whether it is possible to find one way to move that the distance of the two cars never exceeds $$$m$$$.

Let $$$dp[i]$$$ be the set of available positions of one car when the other car is at the $$$i$$$-th position. For example, if the positions are $$$[7,5,2,6]$$$ and $$$m=3$$$, the initial positions are $$$x_1=3,x_2=4$$$, we will have:

• $$$dp[1]=(4)$$$(there is no $$$3$$$ because $$$|7-3|=4>3$$$),
• $$$dp[2]=(4,7)$$$(either transfer from $$$dp[1]$$$ and continue moving the car at $$$7$$$, or stop the car at $$$7$$$ and move the other one),
• $$$dp[3]=(4,5)$$$(we can let one car stop at $$$4$$$ but can't let it stop at $$$7$$$),
• $$$dp[4]=(4,5)$$$(we can't stop a car at $$$2$$$).

If $$$dp[i]$$$ is never empty during the whole process, then $$$m$$$ is a possible answer. This way, the time complexity is $$$O(\log_2n(n^2+n\log_2n))$$$. Note that we transfer every element from $$$dp[i-1]$$$ to get $$$dp[i]$$$ and to copy the set is very slow.

In order to avoid copy the whole set, we should edit on the set directly. We should delete all of the elements that is too far from $$$p_i$$$, and check if the distance between $$$p_{i-1}$$$ and $$$p_i$$$ is no greater than $$$m$$$. It will be easier to understand after reading the code.

The total time complexity is $$$O(n\log_2^2n)$$$.

Code:

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
int p[N];

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, x1, x2;
	cin >> n >> x1 >> x2;
	for (int i = 1; i <= n; ++i) cin >> p[i];
	int l = abs(x1 - x2), r = 1e9 + 7, ans = -1;
	while (l <= r) {
		int m = (l + r) >> 1;
		set<int> dp;
		if (abs(x1 - p[1]) <= m) dp.insert(x1);
		if (abs(x2 - p[1]) <= m) dp.insert(x2);
		bool ok = !dp.empty();
		for (int i = 2; i <= n; ++i) {
			while (!dp.empty() && abs(*dp.begin() - p[i]) > m) dp.erase(dp.begin());
			while (!dp.empty() && abs(*--dp.end() - p[i]) > m) dp.erase(--dp.end());
			if (abs(p[i - 1] - p[i]) <= m) dp.insert(p[i - 1]);
			if (dp.empty()) {
				ok = false;
				break;
			}
		}
		if (ok) ans = m, r = m - 1;
		else l = m + 1;
	}
	cout << ans << '\n';
	return 0;
}