Detecting a subsequence that’s an arithmetic progression, in a sorted sequence

Given an input sequence $L[0..N-1]$, check whether an arithmetic progression of length $ge N/4$ appears as a subsequence of $L$.

This is a significantly easier problem, and I can suggest a very efficient algorithm for you. Let me build up to it by first explaining a few key ideas underlying the algorithm. Idea 1. Given any two elements of $L$, it is easy to extend them to the maximum-length arithmetic progression containing those two elements. In particular, suppose we have $x,y in L$ with $x<y$. Set $d=y-x$. Then we can extend this sequence on the right as the longest prefix of $y+d,y+2d,y+3d,dots$ that is wholly contained in $L$, and we can extend it on the left with the longest prefix of $x-d,x-2d,x-3d,dots$ that is wholly contained in $L$. Idea 2. Say that an arithmetic progression has gap $d$ if the difference between consequence elements of the arithmetic progression is $d$. If $L$ contains an arithmetic progression of length $ge N/4$, then its gap $d$ must satisfy $d le 4(L[N-1]-L[0])/N$. Idea 3. Suppose there is an arithmetic progression of length $ge N/4$, and let $alpha,beta$ denote the start and end index (in $L$) of the subsequence. Since the subsequence has to be of length $ge N/4$, the interval $[alpha,beta]$ must contain one or more of the following numbers: $0.2N$, $0.4N$, $0.6N$, $0.8N$ (rounding all of them to an integer). To give you some intuition for this: Imagine you’re playing Battleship on a $N times 1$ board, and your opponent has a single ship: a super-long battleship, that is $N/4$ cells long. Could you find his battleship? You sure could. It’s only gonna take you 4 shots to find his battleship. You can shoot at cells $0.2N$, $0.4N$, $0.6N$, $0.8N$, and it’s guaranteed that at least one of them will be a hit (that’s Idea 3). Moreover, once you get a single hit, it’s not going to be hard to sink the rest of his battleship (that’s basically Ideas 1 and 2). With these ideas, I’m ready to propose an algorithm:

• Set $d_max gets 4(L[N-1]-L[0])/N$.
• For each $i_0 in {0.2N, 0.4N, 0.6N, 0.8N}$, do:
  • For each $i$ such that $ige i_0$ and $L[i] le L[i_0]+d_max$, do:
    • For each $j$ such that $j>i$ and $L[j] le L[i]+d_max$, do:
      • Extend the arithmetic progression $L[i],L[j]$ on the left and right as far as possible (using Idea 1).
• Look at the longest arithmetic progression found at any point above. If it has length $ge N/4$, then yes, there exists an arithmetic progression of length $ge N/4$. If its length is $< N/4$, then no, there is no arithmetic progression of length $ge N/4$.

Hopefully you can see why this works. Idea 3 means that, if there is an arithmetic progression of length $ge N/4$, then at least one of the indices $i$ that are visited in the above algorithm must be the index of one element of that progression. Moreover, the index of the next element of that progression must be one of the values taken on by $j$ in the innermost loop. Therefore, at some point the pair $L[i],L[j]$ will be a pair of consecutive elements of the arithmetic progression — which is enough to discover that long arithmetic progression. I would expect that this algorithm will typically be very efficient, on real-world data. If all of the integers in $L$ are in the range $[1,M]$, then we know $d_max le 4M/N$. Moreover, the loop over $i$ typically involves about $d_max N/M le 4$ iterations (on average), and similarly for the loop over $j$. So, we expect to perform maybe $5 times 4 times 4 = 80$ iterations of the innermost statement, regardless of $N$, if the data is randomly chosen (and in particular, not adversarily chosen). Consequently, this should be extremely efficient if the data doesn’t conspire against you. It is possible to further improve this algorithm, for instance, to improve its worst-case running time and reduce the opportunity for worst-case data to cause the running time to blow up, at the cost of making the code more complicated. However, I suspect that this simple algorithm might be sufficient for your needs.