Algorithm for determining largest set of successively evenly spaced value of numbers in a sorted array?

Question

For example, in the input array [0,1,4,6,8,9,12] the largest set of successively evenly spaced numbers is {0,4,8,12} and the next largest that isn't a subset of the largest is {4,6,8}.

Answer 1

You can use a two-pass method:

diffarray = []

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

diffarray is :

       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

You can now iterate through all elements in each row, and go "forward" (moving down and right). This can be done recursively; remember to step the same amount of columns as rows.