Algorithm for determining the largest set of sequentially evenly spaced numbers in a sorted array?

Question

For example, in the input array [0,1,4,6,8,9,9,12] the largest set of consecutively uniformly distributed numbers {0,4,8,12} and the next largest that isn’t a subset of the largest - {4, 6.8}.

Answer 1

You can use the two pass method:

diffarray = [] for (i= 0..array.size-2) { for (j= i..array.size-1) { diffarray[i][j] = array[j] - array[i] } } 

diffarray :

  0 1 4 6 8 9 12 [0] [1] [2] [3] [4] [5] [6] 0 [0] . 1 4 6 8 9 12 1 [1] . . 3 5 7 8 11 4 [2] . . . 2 4 5 8 6 [3] . . . . 2 3 6 8 [4] . . . . . 1 4 9 [5] . . . . . . 3 

Now you can iterate over all the elements in each row and move forward (moving down and to the right). This can be done recursively; Remember to make the same number of columns as the rows.