All cities index from left to the right. Let $A1(n)$ be the set of all index, left to index $n$, who has one direct flight. Let $A2(n)$ be the set of all index, left to index $n$, who need one connecting flight.

It is $A2(n)$ to be crucial. When index $n + 1$ is added, a direct flight $n \rightarrow n + 1$ is needed and accordingly $n$ is part of $A1(n + 1)$ and all $A1(n)$ is part of $A2(n + 1)$ and no need flights added for $A1(n)$ . So consider index in $A2(n)$ and the would-be-shrink set of $A2(n + 1)$ be denoted by $X$ staring at $A2(n + 1)$. Let $a2(n)$ be the largest index in $A2(n)$ , with a convenient 0 when $A2(n)$ is empty, so a $a2(n) \rightarrow n + 1$ is wanted/added in $A1(n + 1)$ and $a2(n)$ need to be deleted from $X$. $a2(a2(n)) \rightarrow n + 1$ is wanted/added in $A1(n + 1)$ and $a2(a2(n))$ need to be delete from $X$. $a2(a2(a2(n))) \rightarrow n + 1$ is wanted/added in $A1(n + 1)$ and $a2(a2(a(2)))$ n need to be delete from $X$. And so on so forth.

Starting from two city. $A1(2)=\{1\}, A2(2)=empty$.

3 comes into picture. Temporarily, $A1(3)=\{2\}, A2(3)=\{1\}, a2(1) = 0$ . Final.

4 comes into picture. Temporarily, $A1(4)=\{3\}, A2(4)=\{1,2,3\} - A1(4)=\{1,2\}, a2(3) = 1, A1(4)=\{1,3\}, A2(4)=\{2\}$. Final.

5 comes into picture. Temporarily, $A1(5)=\{4\}, A2(5)=\{1,2,3\}, a2(4) = 2 , A1(5)=\{2,4\}, A2(5)=\{1,3\}$. Final.

Then. Arrange the index from $n$ to 1 rather than from 1 to $n$ to have the backward flight map. So the computation size is 2 times only. So overall, this is the best map. ….

Searching largest index of $A2(n)$ . Being searching, at log(n) by binary search when the set is organized. But?