Return to Revisions

Problem Statement:

Given a set of numbers, find the length of the longest arithmetic progression in it.

Examples: numbers = new int[]{1, 3, 4, 5, 7, 8, 9} The length is 5, and the sequence is 1, 3, 5, 7, 9 with increment 2 in each iteration.

Introduction of the algorithm

The longest arithmetic progressions algorithm can be solved using dynamic programming method. I spent several hours to study the algorithm. I read the paper called "Finding Longest Arithmetic Progressions", base on the author's introduction in the paper, the lower bound algorithm is O(nlogn) based on the algebraic decision tree model of computation. I will try to understand the lower bound algorithm later on.

Dynamic programming

The longest arithmetic progression can be found in O(n²) time using a dynamic programming algorithm similar to the following interesting subproblem , which can be called AVERAGE.

AVERAGE subproblem

It is to determine whether the input contains a three-term arithmetic progression, or equivalently, if any array element is the average of two others.

Test case analysis

I like to use a 7 x 7 matrix to define the lookup table based on the test case {1,3,4,5,7,8,9}.

Base case is to set lookup[i][n-1] = 2 for any i from 0 to n - 1.

0 1 2 3 4 5 6
_________________________
0| 0 0 0 0 0 0 2
1| 0 0 0 0 0 0 2
2| 0 0 0 0 0 0 2
3| 0 0 0 0 0 0 2
4| 0 0 0 0 0 0 2
5| 0 0 0 0 0 0 2
6| 0 0 0 0 0 0 2

Checking out 8, found 7, 8, 9. We have lookup[4][5] = lookup[5][6] + 1.
0 1 2 3 4 5 6
_________________________
0| 0 0 0 0 0 0 2
1| 0 0 0 0 0 0 2
2| 0 0 0 0 0 0 2
3| 0 0 0 0 0 0 2
4| 0 0 0 0 0 3 2
5| 0 0 0 0 0 0 2
6| 0 0 0 0 0 0 2

Practice for mock interview

I was told to practice this algorithm when I practice mock interviews February 18, 2018 weekend. I wrote a C# solution based on the above test case. The algorithm is not too hard, but it is hard for me to come out the idea to define the subproblem AVERAGE the first time.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace TwoPointerTechniques
{
 class Program
 {
 /// <summary>
 /// Based on the code from the following blog:
 /// https://prismoskills.appspot.com/lessons/Dynamic_Programming/Chapter_22_-_Longest_arithmetic_progression.jsp
 /// </summary>
 /// <param name="args"></param>
 static void Main(string[] args)
 {
 var sortedArr = new int[] { 1, 3, 4, 5, 7, 8, 9 };
 var n = sortedArr.Length;
 var lookup = FindArithmeticProgressionLength3(sortedArr);
 Debug.Assert(lookup[0] == 5);
 }
 /// <summary>
 /// How to find if a sorted array contains an Arithmetic Progression (AP) of length 3?
 /// </summary>
 /// <param name="numbers"></param>
 /// <returns></returns>
 public static int[] FindArithmeticProgressionLength3(int[] numbers)
 {
 var n = numbers.Length;
 var lookup = new int[n][];
 for (int i = 0; i < n; i++)
 {
 lookup[i] = new int[n];
 }
 int maxAP = 2;
 int apTerm = 0;
 int apStart = 0;
 // Any 2-letter series is an AP
 // Here we initialize only for the last column of lookup because
 // all i and (n-1) pairs form an AP of size 2 
 for (int i = 0; i < n; i++)
 {
 lookup[i][n - 1] = 2;
 }
 // Loop over the array and find two elements 'left' and 'right' such that 
 // numbers[left] + numbers[right] = 2 * numbers[middle]
 for (int middle = n - 2; middle >= 1; middle--)
 {
 var left = middle - 1;
 var right = middle + 1;
 while (left >= 0 && right <= n - 1)
 {
 int isAP = (numbers[left] + numbers[right]) - 2 * numbers[middle];
 if (isAP < 0)
 {
 right++;
 }
 else if (isAP > 0)
 {
 left--;
 }
 else
 {
 lookup[left][middle] = lookup[middle][right] + 1;
 maxAP = Math.Max(maxAP, lookup[left][middle]);
 if (maxAP == lookup[left][middle])
 {
 // Store the Arithmetic Progression's term
 // And the start point of the AP
 apTerm = numbers[middle] - numbers[left];
 apStart = left;
 }
 right++;
 left--;
 }
 }
 }
 return new int[] { maxAP, apStart, apTerm };
 }
 }
}