Longest Arithmetic Progression Algorithm

Question

Problem Statement: >

Given a sorted array, 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, also I like to read the related question called Longest equally-spaced subsequence on stackoverflow.com.

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. In other words, 8 is the average of 7 and 9, since 8 = (7 + 9)/ 2. This is also a simple example of AVERAGE subproblem.

     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

The idea of applying test case analysis is to tutor myself to learn how to solve the algorithm using dynamic programming method step by step, later on I can apply this technique to other dynamic programming algorithm as well.

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 };
        }
    }
}

Answer 1

In FindArithmeticProgressionLength3 is always an array of dimension n x n. Why did you use jagged arrays instead of

var lookup = new int[n, n];

// several lines skipped ...

for (var i = 0; i < n; i++)
{
    lookup[i, n - 1] = 2;
}

As an 2-dimensional array is only one object compared to n+1 objects with the jagged array you should consider using that. And also the risk of failing to initialize the array (either to forget one of the lookup[n] to allocate or an out-of-Memory exception) is reduced to one single line of Code.