title: Longest arithmetic progression with a hole
body: <p>The longest arithmetic progression subsequence problem is as follows. Given an array of integers A, devise an algorithm to find the longest arithmetic progression in it. In other words find a sequence i1 &lt; i2 &lt; … &lt; ik, such that A[i1], A[i2], …, A[ik] form an arithmetic progression, and k is maximal.  The following code solves the problem in O(n^2) time and space. (Modified from <a href="http://www.geeksforgeeks.org/length-of-the-longest-arithmatic-progression-in-a-sorted-array/" rel="nofollow">http://www.geeksforgeeks.org/length-of-the-longest-arithmatic-progression-in-a-sorted-array/</a> . )</p>
  
  <pre><code>#!/usr/bin/env python
  import sys
  
  def arithmetic(arr):
      n = len(arr)
      if (n&lt;=2):
          return n
  
      llap = 2
  
  
      L = [[0]*n for i in xrange(n)]
      for i in xrange(n):
          L[i][n-1] = 2
  
      for j in xrange(n-2,0,-1):
          i = j-1
          k = j+1
          while (i &gt;=0 and k &lt;= n-1):
              if (arr[i] + arr[k] &lt; 2*arr[j]):
                  k = k + 1
              elif (arr[i] + arr[k] &gt; 2*arr[j]):
                  L[i][j] = 2
                  i -= 1
              else:
  
                  L[i][j] = L[j][k] + 1                   
                  llap = max(llap, L[i][j]) 
                  i = i - 1
                  k = j + 1
  
          while (i &gt;=0):
              L[i][j] = 2
              i -= 1
      return llap
  
  arr = [1,4,5,7,8,10]  
  print arithmetic(arr)
  </code></pre>
  
  <p>This outputs <code>4</code>.</p>
  
  <p>However I would like to be able to find arithmetic progressions where up to one value is missing. So if arr = [1,4,5,8,10,13] I would like it to report that there is a progression of length 5 with one value missing.</p>
  
  <p>Can this be done efficiently?</p>