Remove a single number in the sequence to make it an arithmetic progression.
The number at position i can be removed if the sub-sequence on its left and right are both arithmetic progression and when when we concat that two parts they still make an arithmetic progression.
The first condition can be handled by precalculate f* = whether the prefix of i characters of the sequence is arithmetic progression and similarly g for the suffixes. Put all the corner cases aside the whole conditions can be represented as f* and g* and a[i - 2] - a[i - 1] = a[i - 1] - a[i + 1] = a[i + 1] - a[i + 2] (1).
We will use dynamic programming (dp) to calculate f and g. Since they are similar let’s just discuss how to calculate f. Initialize the dp with f = f = f = true. We’ll have that
- f* = (a[i - 1] - a* = a[i - 2] - a[i - 1] and f[i - 1]).
Before using the formula (1) some corner cases we need to consider is when N ≤ 3, i ≤ 2 and N - 2 ≤ i.
Complexity is O(N).