A Google Problem (2) - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

A Google Problem (2)

A Google Problem (2)# JobHunting - 待字闺中

D*e2011-10-19 07:10

1 楼

Given an array of integers A, give an algorithm to find the longest
Arithmetic progression in it, i.e find a sequence i1 < i2 < … < ik, such
that A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the
largest possible. The sequence S1, S2, …, Sk is called an arithmetic
progression if Sj+1 – Sj is a constant.

i*h2011-10-19 07:10

2 楼

I feel that a sort is necessary, so at least O(NlgN). After that, a brutal
force can solve it in O((N**2)*lgN). Can remove the lgN if hash table is
used.
Simply put, for each element Ai, for each element Aj after Ai, get their
delta, and then check if Aj+delta is in.
Maybe DP is better?

d*l2011-10-19 07:10

3 楼

你这好像是n^3的，对于每个Ai和Aj，你都要检查Aj+d,Aj+2d,Aj+3d。。这样才能找出
哪个最长

【在 i*******h 的大作中提到】

: I feel that a sort is necessary, so at least O(NlgN). After that, a brutal
: force can solve it in O((N**2)*lgN). Can remove the lgN if hash table is
: used.
: Simply put, for each element Ai, for each element Aj after Ai, get their
: delta, and then check if Aj+delta is in.
: Maybe DP is better?

s*n2011-10-19 07:10

4 楼

int findLongestRegression (int array[], int size){
if (size<=0) return 0;
sort (arrary, array+size);
int maxgap = array[size-1]-array[0];
int gap;
int start,next,current;
int k, maxk=0;
for (gap=1;gap<=maxgap;gap++){
for (start=0; startif (array[start]>=array[0]+gap) break;
k=0;
current = start;
for (next=start+1; nextif (array[next]-array[current]==gap){
k++; current = next;
}
}
if (k>maxk) maxk=k;
}
}
return maxk;
}
This algorithm above is not very efficient. The one below is more efficient:
1. sorting
2. for each gap between 1 to maxgap
3. new an array len with size gap-1, len[i] is how long the list of element
% gap == i;
4. divide array into segments, segment_i between [array[0]+*gap,array[0]+(i+
1)*gap]
5. go through each segment, add len[i] if these still new element in the
list_i
This algorithm for each gap is n, so n^2

【在 D*******e 的大作中提到】

: Given an array of integers A, give an algorithm to find the longest
: Arithmetic progression in it, i.e find a sequence i1 < i2 < … < ik, such
: that A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the
: largest possible. The sequence S1, S2, …, Sk is called an arithmetic
: progression if Sj+1 – Sj is a constant.