동일한 간격의 최장 하위 시퀀스

동일한 간격의 최장 하위 시퀀스

---

정렬 된 순서로 백만 개의 정수가 있고 연속 쌍의 차이가 동일한 가장 긴 하위 시퀀스를 찾고 싶습니다. 예를 들면

1, 4, 5, 7, 8, 12

하위 시퀀스가 ​​있습니다

   4,       8, 12

내 순진한 방법은 탐욕스럽고 각 지점에서 하위 시퀀스를 얼마나 멀리 확장 할 수 있는지 확인합니다. 이것은 O(n²)보이는 포인트 당 시간 이 걸립니다 .

이 문제를 해결하는 더 빠른 방법이 있습니까?

최신 정보. 가능한 한 빨리 답변에 제공된 코드를 테스트 할 것입니다 (감사합니다). 그러나 n ^ 2 메모리를 사용하면 작동하지 않는다는 것은 이미 분명합니다. 지금까지 입력으로 끝나는 코드는 없습니다 [random.randint(0,100000) for r in xrange(200000)].

타이밍. 32 비트 시스템에서 다음 입력 데이터로 테스트했습니다.

a= [random.randint(0,10000) for r in xrange(20000)] 
a.sort()

• ZelluX의 동적 프로그래밍 방법은 1.6G의 RAM을 사용하며 2 분 14 초가 걸립니다. pypy를 사용하면 9 초 밖에 걸리지 않습니다! 그러나 큰 입력에서 메모리 오류와 함께 충돌합니다.
• Armin의 O (nd) 시간 방법은 pypy로 9 초가 걸렸지 만 RAM은 20MB에 불과했습니다. 물론 범위가 훨씬 더 크다면 이것은 훨씬 더 나쁠 것입니다. 메모리 사용량이 적다는 것은 a = [random.randint (0,100000) for r in xrange (200000)]로 테스트 할 수 있음을 의미했지만 몇 분 안에 완료되지 않았습니다.

Kluev의 방법을 테스트 할 수 있도록하기 위해

a= [random.randint(0,40000) for r in xrange(28000)] 
a = list(set(a))
a.sort()

대략 길이 목록을 작성합니다 20000. pypy의 모든 타이밍

• ZelluX, 9 초
• Kluev, 20 초
• 아르 민, 52 초

ZelluX 방법이 선형 공간으로 만들어 질 수 있다면 분명 승자가 될 것 같습니다.

---

업데이트 : 여기에 설명 된 첫 번째 알고리즘은 Armin Rigo의 두 번째 답변으로 더 이상 사용되지 않으며 훨씬 간단하고 효율적입니다. 그러나이 두 방법 모두 한 가지 단점이 있습니다. 백만 개의 정수에 대한 결과를 찾으려면 많은 시간이 필요합니다. 그래서 입력 정수의 범위가 제한되어 있다고 가정하는 두 가지 변형을 더 시도했습니다 (이 답변의 후반부 참조). 이러한 제한은 훨씬 더 빠른 알고리즘을 허용합니다. 또한 Armin Rigo의 코드를 최적화하려고했습니다. 마지막에 내 벤치마킹 결과를 참조하십시오.

---

다음은 O (N) 메모리를 사용하는 알고리즘의 아이디어입니다. 시간 복잡도는 O (N ² log N)이지만 O (N ² ) 로 줄일 수 있습니다 .

알고리즘은 다음 데이터 구조를 사용합니다.

1. prev: (불완전한) 하위 시퀀스의 이전 요소를 가리키는 인덱스 배열입니다.
2. hash: 키가있는 해시 맵 = 하위 시퀀스 및 값의 연속 쌍 간의 차이 = 다른 두 해시 맵. 이러한 다른 해시 맵의 경우 : 키 = 하위 시퀀스의 시작 / 종료 인덱스, 값 = 쌍 (서브 시퀀스 길이, 하위 시퀀스의 종료 / 시작 인덱스).
3. pq: prev및에 저장된 하위 시퀀스에 대해 가능한 모든 "차이"값에 대한 우선 순위 대기열 hash.

연산:

1. prev인덱스로 초기화 합니다 i-1. 이 단계에서 찾은 모든 (불완전한) 하위 시퀀스와 해당 "차이점"을 업데이트 hash하고 pq등록합니다.
2. 에서 가장 작은 "차이점"을 가져오고 제거 pq합니다. hash두 번째 수준 해시 맵 중 하나 에서 해당 레코드를 가져 오고 스캔합니다. 이때 주어진 "차이"가있는 모든 하위 시퀀스가 ​​완료됩니다. 두 번째 수준 해시 맵에 지금까지 발견 된 것보다 더 나은 하위 시퀀스 길이가 포함 된 경우 최상의 결과를 업데이트합니다.
3. 배열에서 prev: # 2 단계에서 찾은 시퀀스의 각 요소에 대해 인덱스를 줄이고 업데이트 hash하고 가능하면 pq. 을 업데이트하는 동안 hash다음 작업 중 하나를 수행 할 수 있습니다. 길이가 1 인 새 하위 시퀀스를 추가하거나 기존 하위 시퀀스를 1 씩 늘리거나 기존 하위 시퀀스 두 개를 병합합니다.
4. 2 단계에서 찾은 해시 맵 레코드를 제거합니다.
5. pq비어 있지 않은 동안 2 단계부터 계속합니다 .

이 알고리즘은 각각 O (N)의 O (N) 요소를 업데이트 prev합니다. 그리고 이러한 각 업데이트는에 새로운 "차이점"을 추가해야 할 수 있습니다 pq. 이 모든 것은 .NET 용 간단한 힙 구현을 사용하는 경우 O (N ² log N) 의 시간 복잡성을 의미 합니다 pq. O (N ² )로 줄이려면 더 고급 우선 순위 큐 구현을 사용할 수 있습니다. 가능성 중 일부는이 페이지에 나열되어 있습니다. Priority Queues .

Ideone 에서 해당 Python 코드를 참조하십시오 . 이 코드는 목록에서 중복 요소를 허용하지 않습니다. 이 문제를 고칠 수는 있지만 어쨌든 중복을 제거하고 중복을 넘어서 가장 긴 하위 시퀀스를 개별적으로 찾는 것이 좋은 최적화가 될 것입니다.

그리고 약간의 최적화 후 동일한 코드 . 여기서 검색은 가능한 하위 시퀀스 "차이"를 곱한 하위 시퀀스 길이가 소스 목록 범위를 초과하는 즉시 종료됩니다.

---

Armin Rigo의 코드는 간단하고 매우 효율적입니다. 그러나 어떤 경우에는 피할 수있는 추가 계산을 수행합니다. 하위 시퀀스 길이에 가능한 하위 시퀀스 "차이"를 곱한 값이 소스 목록 범위를 초과하는 즉시 검색이 종료 될 수 있습니다.

def findLESS(A):
  Aset = set(A)
  lmax = 2
  d = 1
  minStep = 0

  while (lmax - 1) * minStep <= A[-1] - A[0]:
    minStep = A[-1] - A[0] + 1
    for j, b in enumerate(A):
      if j+d < len(A):
        a = A[j+d]
        step = a - b
        minStep = min(minStep, step)
        if a + step in Aset and b - step not in Aset:
          c = a + step
          count = 3
          while c + step in Aset:
            c += step
            count += 1
          if count > lmax:
            lmax = count
    d += 1

  return lmax

print(findLESS([1, 4, 5, 7, 8, 12]))

---

소스 데이터 (M)의 정수 범위가 작 으면 O (M ² ) 시간 및 O (M) 공간 으로 간단한 알고리즘이 가능 합니다.

def findLESS(src):
  r = [False for i in range(src[-1]+1)]
  for x in src:
    r[x] = True

  d = 1
  best = 1

  while best * d < len(r):
    for s in range(d):
      l = 0

      for i in range(s, len(r), d):
        if r[i]:
          l += 1
          best = max(best, l)
        else:
          l = 0

    d += 1

  return best


print(findLESS([1, 4, 5, 7, 8, 12]))

Armin Rigo의 첫 번째 방법과 유사하지만 동적 데이터 구조를 사용하지 않습니다. 원본 데이터에 중복이 없다고 생각합니다. 그리고 (코드를 간단하게 유지하기 위해) 최소 입력 값이 음수가 아니고 0에 가깝다고 가정합니다.

---

부울 배열 대신 비트 셋 데이터 구조와 비트 연산을 사용하여 데이터를 병렬로 처리하면 이전 알고리즘이 개선 될 수 있습니다. 아래에 표시된 코드는 내장 Python 정수로 bitset을 구현합니다. 동일한 가정이 있습니다. 중복이없고 최소 입력 값이 음수가 아니고 0에 가깝습니다. 시간 복잡도는 O (M ² * log L)입니다. 여기서 L은 최적 하위 시퀀스의 길이이고 공간 복잡도는 O (M)입니다.

def findLESS(src):
  r = 0
  for x in src:
    r |= 1 << x

  d = 1
  best = 1

  while best * d < src[-1] + 1:
    c = best
    rr = r

    while c & (c-1):
      cc = c & -c
      rr &= rr >> (cc * d)
      c &= c-1

    while c != 1:
      c = c >> 1
      rr &= rr >> (c * d)

    rr &= rr >> d

    while rr:
      rr &= rr >> d
      best += 1

    d += 1

  return best

---

벤치 마크 :

입력 데이터 (약 100,000 개의 정수)는 다음과 같이 생성됩니다.

random.seed(42)
s = sorted(list(set([random.randint(0,200000) for r in xrange(140000)])))

그리고 가장 빠른 알고리즘을 위해 다음 데이터 (약 1000000 정수)도 사용했습니다.

s = sorted(list(set([random.randint(0,2000000) for r in xrange(1400000)])))

모든 결과는 시간을 초 단위로 표시합니다.

Size:                         100000   1000000
Second answer by Armin Rigo:     634         ?
By Armin Rigo, optimized:         64     >5000
O(M^2) algorithm:                 53      2940
O(M^2*L) algorithm:                7       711

---

우리는 O(n*m)당신의 것을 조정함으로써 아주 적은 메모리 필요로 적시에 해결책 을 가질 수 있습니다. 다음 n은 주어진 숫자 입력 시퀀스의 항목 수이며 m범위입니다. 즉, 가장 높은 숫자에서 가장 낮은 숫자를 뺀 값입니다.

A를 모든 입력 번호의 순서로 호출하십시오 (그리고 미리 계산 된 번호를 사용하여 set()"이 번호가 A에 있습니까?"라는 질문에 일정한 시간에 대답하십시오). d를 우리가 찾고있는 하위 시퀀스 의 단계 (이 하위 시퀀스의 두 숫자 간의 차이)라고 부릅니다 . d의 가능한 모든 값에 대해 모든 입력 번호에 대해 다음 선형 스캔을 수행합니다. A에서 오는 모든 숫자 n에 대해 오름차순으로 숫자가 아직 표시되지 않은 경우 A에서 n에서 시작하는 시퀀스의 길이를 a 단계 d. 그런 다음 해당 시퀀스의 모든 항목을 이미 본대로 표시하여 동일한 d에 대해 다시 검색하지 않도록합니다. 이 때문에 복잡성은 O(n)d의 모든 값에 해당합니다.

A = [1, 4, 5, 7, 8, 12]    # in sorted order
Aset = set(A)

for d in range(1, 12):
    already_seen = set()
    for a in A:
        if a not in already_seen:
            b = a
            count = 1
            while b + d in Aset:
                b += d
                count += 1
                already_seen.add(b)
            print "found %d items in %d .. %d" % (count, a, b)
            # collect here the largest 'count'

업데이트 :

• 이 솔루션은 상대적으로 작은 d 값에만 관심이있는 경우 충분할 수 있습니다. 예를 들어, 최상의 결과를 얻는 d <= 1000것이 충분하다면. 그런 다음 복잡성은 O(n*1000). 이것은 알고리즘을 근사치로 만들지 만 실제로 n=1000000. (CPython의 경우 400-500 초, PyPy의 경우 80-90 초, 0에서 10,000,000 사이의 임의의 숫자 하위 집합으로 측정 됨)

• 여전히 전체 범위를 검색하고 싶고 긴 시퀀스가 ​​존재하는 일반적인 경우라면 d가 너무 커서 더 긴 시퀀스를 찾을 수없는 즉시 중지하는 것이 눈에 띄는 개선점입니다.

---

업데이트 :이 문제에 대한 논문을 찾았 습니다 . 여기에서 다운로드 할 수 있습니다 .

다음은 동적 프로그래밍에 기반한 솔루션입니다. O (n ^ 2) 시간 복잡성과 O (n ^ 2) 공간 복잡성이 필요하며 해싱을 사용하지 않습니다.

모든 숫자가 a오름차순으로 배열 에 저장되어 있다고 가정 n하고 길이를 저장합니다. 2D 배열은 l[i][j]최장 등 간격의 시퀀스 길이가 끝나는 정의 a[i]하고 a[j], 그리고 l[j][k]= l[i][j]+ 1이면 a[j]- a[i]= a[k]- a[j](ⅰ <J <K).

lmax = 2
l = [[2 for i in xrange(n)] for j in xrange(n)]
for mid in xrange(n - 1):
    prev = mid - 1
    succ = mid + 1
    while (prev >= 0 and succ < n):
        if a[prev] + a[succ] < a[mid] * 2:
            succ += 1
        elif a[prev] + a[succ] > a[mid] * 2:
            prev -= 1
        else:
            l[mid][succ] = l[prev][mid] + 1
            lmax = max(lmax, l[mid][succ])
            prev -= 1
            succ += 1

print lmax

---

연산

• 목록을 순회하는 메인 루프
• 사전 계산 목록에서 숫자가 발견되면 해당 목록에있는 모든 시퀀스에 속하고 카운트 + 1로 모든 시퀀스를 다시 계산합니다.
• 현재 요소에 대해 미리 계산 된 모든 항목 제거
• 첫 번째 요소가 0에서 현재까지의 범위이고 두 번째가 현재 순회 요소 인 새 시퀀스를 다시 계산합니다 (실제로는 0에서 현재까지가 아니라 새 요소가 max (a) 및 new보다 크면 안된다는 사실을 사용할 수 있습니다. 목록은 이미 찾은 것보다 길어질 가능성이 있어야합니다)

따라서 목록 [1, 2, 4, 5, 7]출력의 경우 (조금 지저분합니다. 직접 코드를 작성하고 확인하십시오)

• 인덱스 0 , 요소 1 :
  • 경우 1precalc에서? 아니요-아무것도하지 않습니다.
  • 아무것도하지 마세요
• 인덱스 1 , 요소 2 :
  • 경우 2precalc에서? 아니요-아무것도하지 않습니다.
  • 3 = 1+ ( 2- 1) * 2 인지 확인하십시오 . 아니요-아무것도하지 않습니다.
• 인덱스 2 , 요소 4 :
  • 경우 4precalc에서? 아니요-아무것도하지 않습니다.
    • 6 = 2+ ( 4- 2) * 2 인지 확인하십시오 . 아니
    • 우리 세트에서 7 = 1+ ( 4- 1) * 2 인지 확인하십시오 . 예-새 요소 추가 {7: {3: {'count': 2, 'start': 1}}} 7-목록의 요소, 3은 단계입니다.
• 인덱스 3 , 요소 5:
  • 경우 5precalc에서? 아니요-아무것도하지 않습니다.
    • 6 = 4 + ( - ) * 2가 계산 된 요소 7 보다 작기 4때문에 확인하지 마십시오.54
    • 우리 세트에서 8 = 2+ ( 5- 2) * 2 인지 확인하십시오 . 아니
    • check 10 = 2+ ( 5- 1) * 2-max (a) == 7 이상
• 인덱스 4 , 요소 7:
  • 경우 7 precalc에서? 예-결과에 입력
    • 선택하지 5인해 9 = 5 + ( 7- 5) 2 개보다 최대 * (a) == 7

result = (3, { 'count': 3, 'start': 1}) # step 3, count 3, start 1, turn it into sequence

복잡성

O (N ^ 2) 이상이되어서는 안되며, 새로운 sequencies 검색이 일찍 종료 되었기 때문에 적다고 생각합니다. 나중에 자세한 분석을 제공하겠습니다.

암호

def add_precalc(precalc, start, step, count, res, N):
    if step == 0: return True
    if start + step * res[1]["count"] > N: return False

    x = start + step * count
    if x > N or x < 0: return False

    if precalc[x] is None: return True

    if step not in precalc[x]:
        precalc[x][step] = {"start":start, "count":count}

    return True

def work(a):
    precalc = [None] * (max(a) + 1)
    for x in a: precalc[x] = {}
    N, m = max(a), 0
    ind = {x:i for i, x in enumerate(a)}

    res = (0, {"start":0, "count":0})
    for i, x in enumerate(a):
        for el in precalc[x].iteritems():
            el[1]["count"] += 1
            if el[1]["count"] > res[1]["count"]: res = el
            add_precalc(precalc, el[1]["start"], el[0], el[1]["count"], res, N)
            t = el[1]["start"] + el[0] * el[1]["count"]
            if t in ind and ind[t] > m:
                m = ind[t]
        precalc[x] = None

        for y in a[i - m - 1::-1]:
            if not add_precalc(precalc, y, x - y, 2, res, N): break

    return [x * res[0] + res[1]["start"] for x in range(res[1]["count"])]

---

여기에 또 다른 대답이 O(n^2)있습니다. 목록을 세트로 전환하는 것 이상의 주목할만한 메모리 요구 사항없이 제 시간에 작업 합니다.

아이디어는 매우 순진합니다. 원본 포스터처럼 탐욕스럽고 각 포인트 쌍에서 하위 시퀀스를 얼마나 확장 할 수 있는지 확인합니다.하지만 먼저 하위 시퀀스 의 시작 부분 에 있는지 확인 합니다. 점에서 즉, a그리고 b당신은 멀리 확장 할 수있는 방법을 확인하려면 b + (b-a), b + 2*(b-a), ...하지만 경우에만 a - (b-a)모든 점들의 집합에없는. 그렇다면 이미 동일한 하위 시퀀스를 본 것입니다.

비결은이 간단한 최적화만으로도 O(n^2)원본에서 복잡성을 낮추기에 충분하다는 것을 스스로 확신하는 것입니다 O(n^3). 그것은 독자들에게 연습으로 남았습니다. :-) 시간은 O(n^2)여기 에서 다른 솔루션 과 경쟁적입니다 .

A = [1, 4, 5, 7, 8, 12]    # in sorted order
Aset = set(A)

lmax = 2
for j, b in enumerate(A):
    for i in range(j):
        a = A[i]
        step = b - a
        if b + step in Aset and a - step not in Aset:
            c = b + step
            count = 3
            while c + step in Aset:
                c += step
                count += 1
            #print "found %d items in %d .. %d" % (count, a, c)
            if count > lmax:
                lmax = count

print lmax

---

당신의 해결책은 O(N^3)지금입니다 (당신은 말했습니다 O(N^2) per index). 여기 O(N^2)에 시간과 O(N^2)기억 솔루션이 있습니다.

생각

우리가 인덱스 통과 서브 순서를 알고있는 경우에 i[0], i[1], i[2], i[3]우리가 서브를 시도해서는 안 그와 함께 시작 i[1]하고 i[2]나 i[2]하고i[3]

참고 a정렬 된 항목을 사용하여 좀 더 쉽게 코드를 편집 했지만 동일한 요소에 대해서는 작동하지 않습니다. 동일한 요소의 최대 개수를 O(N)쉽게 확인할 수 있습니다.

의사 코드

나는 최대 길이만을 찾고 있지만 아무것도 변경하지 않습니다.

whereInA = {}
for i in range(n):
   whereInA[a[i]] = i; // It doesn't matter which of same elements it points to

boolean usedPairs[n][n];

for i in range(n):
    for j in range(i + 1, n):
       if usedPair[i][j]:
          continue; // do not do anything. It was in one of prev sequences.

    usedPair[i][j] = true;

    //here quite stupid solution:
    diff = a[j] - a[i];
    if diff == 0:
       continue; // we can't work with that
    lastIndex = j
    currentLen = 2
    while whereInA contains index a[lastIndex] + diff :
        nextIndex = whereInA[a[lastIndex] + diff]
        usedPair[lastIndex][nextIndex] = true
        ++currentLen
        lastIndex = nextIndex

    // you may store all indicies here
    maxLen = max(maxLen, currentLen)

메모리 사용에 대한 생각

O(n^2)1000000 요소의 경우 시간이 매우 느립니다. 그러나 이러한 수의 요소에서이 코드를 실행하려는 경우 가장 큰 문제는 메모리 사용량입니다.
그것을 줄이기 위해 무엇을 할 수 있습니까?

• 부울 배열을 비트 필드로 변경하여 비트 당 더 많은 부울을 저장하십시오.
• 우리는 단지 사용하기 때문에 다음의 각 부울 배열이 짧게 usedPairs[i][j]경우i < j

몇 가지 휴리스틱 :

• 사용 된 인덱스 쌍만 저장하십시오. (첫 번째 아이디어와의 충돌)
• (예위한 그 이상 사용되지 않습니다 제거 usedPairs i, j이미 루프에 선택되었다)

---

이것은 나의 2 센트입니다.

input이라는 목록이있는 경우 :

input = [1, 4, 5, 7, 8, 12]

이 포인트 (첫 번째 포인트 제외) 각각에 대해 이전 포인트와의 거리를 알려주는 데이터 구조를 만들 수 있습니다.

[1, 4, 5, 7, 8, 12]
 x  3  4  6  7  11   # distance from point i to point 0
 x  x  1  3  4   8   # distance from point i to point 1
 x  x  x  2  3   7   # distance from point i to point 2
 x  x  x  x  1   5   # distance from point i to point 3
 x  x  x  x  x   4   # distance from point i to point 4

이제 열이 있으므로 i-th입력 항목 ( input[i])과 n해당 열의 각 숫자 를 고려할 수 있습니다 .

포함 등거리 일련의 숫자에 속하는 숫자는 input[i]가지고있는 것들이다 n * j에 i-th자신의 컬럼의 위치를 j왼쪽에서 오른쪽으로 열을 이동할 때 이미 발견 일치의 수를 더한 값이다 k-th의 전신은 input[i], k의 인덱스 n의 열에 input[i]있습니다.

예 : 우리가 고려하는 경우 i = 1, input[i] = 4, n = 3, 다음, 우리가 이해하는 시퀀스를 식별 할 수 있습니다 4( input[i],) 7(그것은이 있기 때문에 3위치 1의 열) 및 1때문에, k0 우리의 첫 번째 전신을, 그래서 i.

가능한 구현 (코드가 설명과 동일한 표기법을 사용하지 않는 경우 죄송합니다) :

def build_columns(l):
    columns = {}
    for x in l[1:]:
        col = []
        for y in l[:l.index(x)]:
            col.append(x - y)
        columns[x] = col
    return columns

def algo(input, columns):
    seqs = []
    for index1, number in enumerate(input[1:]):
        index1 += 1 #first item was sliced
        for index2, distance in enumerate(columns[number]):
            seq = []
            seq.append(input[index2]) # k-th pred
            seq.append(number)
            matches = 1
            for successor in input[index1 + 1 :]:
                column = columns[successor]
                if column[index1] == distance * matches:
                    matches += 1
                    seq.append(successor)
            if (len(seq) > 2):
                seqs.append(seq)
    return seqs

가장 긴 것 :

print max(sequences, key=len)

---

배열을 가로 질러 최적의 결과를 기록하고

(1) 인덱스-시퀀스의 요소 차이,
(2) 카운트-지금까지 시퀀스의 요소 수,
(3) 마지막으로 기록 된 요소가있는 테이블을 유지합니다. 요소.

각 배열 요소에 대해 이전 각 배열 요소와의 차이점을 살펴보십시오. 해당 요소가 테이블에서 색인화 된 시퀀스에서 마지막 인 경우 테이블에서 해당 시퀀스를 조정하고 적용 가능한 경우 최상의 시퀀스를 업데이트합니다. 그렇지 않으면 현재 최대 값이 가능한 시퀀스의 길이보다 크지 않는 한 새 시퀀스를 시작합니다.

뒤로 스캔하면 d가 배열 범위의 중간보다 클 때 스캔을 중지 할 수 있습니다. 또는 현재 최대 값이 가능한 시퀀스의 길이보다 클 때, d는 가장 큰 인덱스 차이보다 큽니다. 시퀀스 s[j]의 마지막 요소보다 큰 시퀀스는 삭제됩니다.

내 코드를 JavaScript에서 Python으로 변환했습니다 (첫 번째 Python 코드).

import random
import timeit
import sys

#s = [1,4,5,7,8,12]
#s = [2, 6, 7, 10, 13, 14, 17, 18, 21, 22, 23, 25, 28, 32, 39, 40, 41, 44, 45, 46, 49, 50, 51, 52, 53, 63, 66, 67, 68, 69, 71, 72, 74, 75, 76, 79, 80, 82, 86, 95, 97, 101, 110, 111, 112, 114, 115, 120, 124, 125, 129, 131, 132, 136, 137, 138, 139, 140, 144, 145, 147, 151, 153, 157, 159, 161, 163, 165, 169, 172, 173, 175, 178, 179, 182, 185, 186, 188, 195]
#s = [0, 6, 7, 10, 11, 12, 16, 18, 19]

m = [random.randint(1,40000) for r in xrange(20000)]
s = list(set(m))
s.sort()

lenS = len(s)
halfRange = (s[lenS-1] - s[0]) // 2

while s[lenS-1] - s[lenS-2] > halfRange:
    s.pop()
    lenS -= 1
    halfRange = (s[lenS-1] - s[0]) // 2

while s[1] - s[0] > halfRange:
    s.pop(0)
    lenS -=1
    halfRange = (s[lenS-1] - s[0]) // 2

n = lenS

largest = (s[n-1] - s[0]) // 2
#largest = 1000 #set the maximum size of d searched

maxS = s[n-1]
maxD = 0
maxSeq = 0
hCount = [None]*(largest + 1)
hLast = [None]*(largest + 1)
best = {}

start = timeit.default_timer()

for i in range(1,n):

    sys.stdout.write(repr(i)+"\r")

    for j in range(i-1,-1,-1):
        d = s[i] - s[j]
        numLeft = n - i
        if d != 0:
            maxPossible = (maxS - s[i]) // d + 2
        else:
            maxPossible = numLeft + 2
        ok = numLeft + 2 > maxSeq and maxPossible > maxSeq

        if d > largest or (d > maxD and not ok):
            break

        if hLast[d] != None:
            found = False
            for k in range (len(hLast[d])-1,-1,-1):
                tmpLast = hLast[d][k]
                if tmpLast == j:
                    found = True
                    hLast[d][k] = i
                    hCount[d][k] += 1
                    tmpCount = hCount[d][k]
                    if tmpCount > maxSeq:
                        maxSeq = tmpCount
                        best = {'len': tmpCount, 'd': d, 'last': i}
                elif s[tmpLast] < s[j]:
                    del hLast[d][k]
                    del hCount[d][k]
            if not found and ok:
                hLast[d].append(i)
                hCount[d].append(2)
        elif ok:
            if d > maxD: 
                maxD = d
            hLast[d] = [i]
            hCount[d] = [2]


end = timeit.default_timer()
seconds = (end - start)

#print (hCount)
#print (hLast)
print(best)
print(seconds)

---

This is a particular case for the more generic problem described here: Discover long patterns where K=1 and is fixed. It is demostrated there that it can be solved in O(N^2). Runnig my implementation of the C algorithm proposed there it takes 3 seconds to find the solution for N=20000 and M=28000 in my 32bit machine.

---

Greedy method
1 .Only one sequence of decision is generated.
2. Many number of decisions are generated. Dynamic programming 1. It does not guarantee to give an optimal solution always.
2. It definitely gives an optimal solution.

참고URL : https://stackoverflow.com/questions/18159911/longest-equally-spaced-subsequence