Алгоритм определения наибольшего набора последовательно равномерно распределенных значений чисел в отсортированном массиве?

Question

Например, во входном массиве [0,1,4,6,8,9,12] самый большой набор последовательно равномерно распределенных чисел равен {0,4,8,12}, а следующий по величине, который не ' t подмножество наибольшего - {4,6,8}.

Answer 1

Вы можете использовать двухпроходный метод:

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

Теперь вы можете перебирать все элементы в каждом ряду и двигаться вперед (двигаясь вниз и вправо). Это может быть сделано рекурсивно; не забывайте добавлять одинаковое количество столбцов к строкам.