Ответ 1
Обновление
Я сделал усовершенствование алгоритма, что он принимает среднее значение O (M + N ^ 2) и потребности в памяти O (M + N). В основном это то же, что описанный ниже протокол, но для вычисления возможных факторов A, K для ech diference D, я предварительно загружаю таблицу. Эта таблица занимает меньше секунды для построения M = 10 ^ 7.
Я сделал реализацию C, которая занимает менее 10 минут, чтобы решить N = 10 ^ 5 различных случайных целых элементов.
Вот исходный код в C: Для выполнения просто выполните: gcc -O3 -o findgeo findgeo.c
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <memory.h>
#include <time.h>
struct Factor {
int a;
int k;
struct Factor *next;
};
struct Factor *factors = 0;
int factorsL=0;
void ConstructFactors(int R) {
int a,k,C;
int R2;
struct Factor *f;
float seconds;
clock_t end;
clock_t start = clock();
if (factors) free(factors);
factors = malloc (sizeof(struct Factor) *((R>>1) + 1));
R2 = R>>1 ;
for (a=0;a<=R2;a++) {
factors[a].a= a;
factors[a].k=1;
factors[a].next=NULL;
}
factorsL=R2+1;
R2 = floor(sqrt(R));
for (k=2; k<=R2; k++) {
a=1;
C=a*k*(k+1);
while (C<R) {
C >>= 1;
f=malloc(sizeof(struct Factor));
*f=factors[C];
factors[C].a=a;
factors[C].k=k;
factors[C].next=f;
a++;
C=a*k*(k+1);
}
}
end = clock();
seconds = (float)(end - start) / CLOCKS_PER_SEC;
printf("Construct Table: %f\n",seconds);
}
void DestructFactors() {
int i;
struct Factor *f;
for (i=0;i<factorsL;i++) {
while (factors[i].next) {
f=factors[i].next->next;
free(factors[i].next);
factors[i].next=f;
}
}
free(factors);
factors=NULL;
factorsL=0;
}
int ipow(int base, int exp)
{
int result = 1;
while (exp)
{
if (exp & 1)
result *= base;
exp >>= 1;
base *= base;
}
return result;
}
void findGeo(int **bestSolution, int *bestSolutionL,int *Arr, int L) {
int i,j,D;
int mustExistToBeBetter;
int R=Arr[L-1]-Arr[0];
int *possibleSolution;
int possibleSolutionL=0;
int exp;
int NextVal;
int idx;
int kMax,aMax;
float seconds;
clock_t end;
clock_t start = clock();
kMax = floor(sqrt(R));
aMax = floor(R/2);
ConstructFactors(R);
*bestSolutionL=2;
*bestSolution=malloc(0);
possibleSolution = malloc(sizeof(int)*(R+1));
struct Factor *f;
int *H=malloc(sizeof(int)*(R+1));
memset(H,0, sizeof(int)*(R+1));
for (i=0;i<L;i++) {
H[ Arr[i]-Arr[0] ]=1;
}
for (i=0; i<L-2;i++) {
for (j=i+2; j<L; j++) {
D=Arr[j]-Arr[i];
if (D & 1) continue;
f = factors + (D >>1);
while (f) {
idx=Arr[i] + f->a * f->k - Arr[0];
if ((f->k <= kMax)&& (f->a<aMax)&&(idx<=R)&&H[idx]) {
if (f->k ==1) {
mustExistToBeBetter = Arr[i] + f->a * (*bestSolutionL);
} else {
mustExistToBeBetter = Arr[i] + f->a * f->k * (ipow(f->k,*bestSolutionL) - 1)/(f->k-1);
}
if (mustExistToBeBetter< Arr[L-1]+1) {
idx= floor(mustExistToBeBetter - Arr[0]);
} else {
idx = R+1;
}
if ((idx<=R)&&H[idx]) {
possibleSolution[0]=Arr[i];
possibleSolution[1]=Arr[i] + f->a*f->k;
possibleSolution[2]=Arr[j];
possibleSolutionL=3;
exp = f->k * f->k * f->k;
NextVal = Arr[j] + f->a * exp;
idx=NextVal - Arr[0];
while ( (idx<=R) && H[idx]) {
possibleSolution[possibleSolutionL]=NextVal;
possibleSolutionL++;
exp = exp * f->k;
NextVal = NextVal + f->a * exp;
idx=NextVal - Arr[0];
}
if (possibleSolutionL > *bestSolutionL) {
free(*bestSolution);
*bestSolution = possibleSolution;
possibleSolution = malloc(sizeof(int)*(R+1));
*bestSolutionL=possibleSolutionL;
kMax= floor( pow (R, 1/ (*bestSolutionL) ));
aMax= floor(R / (*bestSolutionL));
}
}
}
f=f->next;
}
}
}
if (*bestSolutionL == 2) {
free(*bestSolution);
possibleSolutionL=0;
for (i=0; (i<2)&&(i<L); i++ ) {
possibleSolution[possibleSolutionL]=Arr[i];
possibleSolutionL++;
}
*bestSolution = possibleSolution;
*bestSolutionL=possibleSolutionL;
} else {
free(possibleSolution);
}
DestructFactors();
free(H);
end = clock();
seconds = (float)(end - start) / CLOCKS_PER_SEC;
printf("findGeo: %f\n",seconds);
}
int compareInt (const void * a, const void * b)
{
return *(int *)a - *(int *)b;
}
int main(void) {
int N=100000;
int R=10000000;
int *A = malloc(sizeof(int)*N);
int *Sol;
int SolL;
int i;
int *S=malloc(sizeof(int)*R);
for (i=0;i<R;i++) S[i]=i+1;
for (i=0;i<N;i++) {
int r = rand() % (R-i);
A[i]=S[r];
S[r]=S[R-i-1];
}
free(S);
qsort(A,N,sizeof(int),compareInt);
/*
int step = floor(R/N);
A[0]=1;
for (i=1;i<N;i++) {
A[i]=A[i-1]+step;
}
*/
findGeo(&Sol,&SolL,A,N);
printf("[");
for (i=0;i<SolL;i++) {
if (i>0) printf(",");
printf("%d",Sol[i]);
}
printf("]\n");
printf("Size: %d\n",SolL);
free(Sol);
free(A);
return EXIT_SUCCESS;
}
Demostration
Я попытаюсь продемонстрировать, что предложенный мной алгоритм 
в среднем для равномерно распределенной случайной последовательности. Я не математик, и я не привык делать подобные демонстрации, поэтому, пожалуйста, заполните, чтобы исправить мне любую ошибку, которую вы можете видеть.
Существует 4 отступованных петель, два первых - коэффициент N ^ 2. M - для вычисления таблицы возможных факторов).
Третий цикл выполняется только один раз в среднем для каждой пары. Вы можете увидеть это, проверяя размер таблицы предварительно рассчитанных факторов. Его размер M, когда N- > inf. Таким образом, средние шаги для каждой пары составляют M/M = 1.
Итак, доказательство проверяет, что четвертый цикл. (Тот, который пересекает добрые последовательности, выполняется меньше или равен O (N ^ 2) для всех пар.
Чтобы продемонстрировать это, я рассмотрю два случая: один, где M → N и другие, где M ~ = N. Где M - максимальная разница исходного массива: M = S (n) -S (1).
В первом случае (M → N) вероятность найти совпадение равна p = N/M. Чтобы начать последовательность, она должна совпадать с вторым и элементом b + 1, где b - длина самой лучшей последовательности до сих пор. Таким образом, цикл будет вводить 
раз. И средняя длина этой серии (предполагая бесконечный ряд) равна 
. Таким образом, общее количество циклов, которые будет выполняться, будет 
. И это близко к 0, когда M → N. Проблема здесь в том, что M ~ = N.
Теперь рассмотрим этот случай, когда M ~ = N. Предположим, что b - лучшая длина последовательности до сих пор. Для случая A = k = 1 последовательность должна начинаться до N-b, поэтому число последовательностей будет N-b, а времена, которые будут проходить для цикла, будут максимальны (N-b) * b.
При A > 1 и k = 1 мы можем экстраполировать на 
, где d - M/N (среднее расстояние между числами). Если мы добавим для всех As от 1 до dN/b, то мы увидим верхний предел:
Для случаев, когда k >= 2, мы видим, что последовательность должна начинаться до 
, поэтому цикл будет вводить среднее значение 
и добавление для всех As от 1 до dN/k ^ b, это дает предел
Здесь худший случай, когда b минимален. Поскольку мы рассматриваем минимальные ряды, рассмотрим очень худший случай b = 2, поэтому число проходов для 4-го цикла для данного k будет меньше
.
И если мы добавим все ks от 2 до бесконечности, получим:
Итак, добавив все проходы для k = 1 и k >= 2, мы имеем максимум:
<Т411 >
Заметим, что d = M/N = 1/p.
Итак, у нас есть два предела: один, который переходит в бесконечность, когда d = 1/p = M/N переходит в 1, а другой - бесконечен, когда d переходит в бесконечность. Таким образом, наш предел - это минимум обоих, и худший случай - когда пересекаются оба круга. Поэтому, если мы решим уравнение:
мы видим, что максимум равен d = 1.353
Таким образом, показано, что четвертые петли будут обрабатываться менее 1,55 Н ^ 2 раза.
Конечно, это для среднего случая. В худшем случае я не могу найти способ генерировать ряды, чей четвертый цикл выше O (N ^ 2), и я твердо верю, что они не существуют, но я не математик, чтобы это доказать.
Старый ответ
Вот решение в среднем O ((n ^ 2) * cube_root (M)), где M - разность между первым и последним элементами массива. И требования к памяти O (M + N).
1. Построить массив H длины M, так что M [i-S [0]] = true, если я существует в начальном массиве и false, если он не существует.
2.- Для каждой пары в массиве S [j] S [i] do:
2.1 Проверьте, может ли это быть первым и третьим элементом возможного решения. Для этого вычислите все возможные пары A, K, которые удовлетворяют уравнению S (i) = S (j) + AK + AK ^ 2. Проверьте этот вопрос SO, чтобы узнать, как решить эту проблему. И убедитесь, что существуют второй элемент: S [i] + A * K
2.2. Проверьте также, что существует элемент с одной позицией, что лучшее решение, которое у нас есть. Например, если наилучшее решение, которое мы имеем до сих пор, состоит из 4 элементов, то проверьте, существуют ли элементы A [j] + AK + AK ^ 2 + AK ^ 3 + AK ^ 4
2.3 Если значения 2.1 и 2.2 истинны, то итерации, сколько времени этот ряд и устанавливается как bestSolution до сих пор, длиннее последнего.
Вот код в javascript:
function getAKs(A) {
if (A / 2 != Math.floor(A / 2)) return [];
var solution = [];
var i;
var SR3 = Math.pow(A, 1 / 3);
for (i = 1; i <= SR3; i++) {
var B, C;
C = i;
B = A / (C * (C + 1));
if (B == Math.floor(B)) {
solution.push([B, C]);
}
B = i;
C = (-1 + Math.sqrt(1 + 4 * A / B)) / 2;
if (C == Math.floor(C)) {
solution.push([B, C]);
}
}
return solution;
}
function getBestGeometricSequence(S) {
var i, j, k;
var bestSolution = [];
var H = Array(S[S.length-1]-S[0]);
for (i = 0; i < S.length; i++) H[S[i] - S[0]] = true;
for (i = 0; i < S.length; i++) {
for (j = 0; j < i; j++) {
var PossibleAKs = getAKs(S[i] - S[j]);
for (k = 0; k < PossibleAKs.length; k++) {
var A = PossibleAKs[k][0];
var K = PossibleAKs[k][17];
var mustExistToBeBetter;
if (K==1) {
mustExistToBeBetter = S[j] + A * bestSolution.length;
} else {
mustExistToBeBetter = S[j] + A * K * (Math.pow(K,bestSolution.length) - 1)/(K-1);
}
if ((H[S[j] + A * K - S[0]]) && (H[mustExistToBeBetter - S[0]])) {
var possibleSolution=[S[j],S[j] + A * K,S[i]];
exp = K * K * K;
var NextVal = S[i] + A * exp;
while (H[NextVal - S[0]] === true) {
possibleSolution.push(NextVal);
exp = exp * K;
NextVal = NextVal + A * exp;
}
if (possibleSolution.length > bestSolution.length) {
bestSolution = possibleSolution;
}
}
}
}
}
return bestSolution;
}
//var A= [ 1, 2, 3,5,7, 15, 27, 30,31, 81];
var A=[];
for (i=1;i<=3000;i++) {
A.push(i);
}
var sol=getBestGeometricSequence(A);
$("#result").html(JSON.stringify(sol));
Вы можете проверить код здесь: http://jsfiddle.net/6yHyR/1/
Я поддерживаю другое решение, потому что считаю, что лучше, когда M очень большой по сравнению с N.