fork download
copy 
  1. import random
  2. import heapq
  3.  
  4. heap = []
  5. subseqs = {}
  6. prevElem = []
  7. bestL = 0
  8.  
  9.  
  10. def merge(x, p, rec):
  11.   length1 = rec[1][p][0]
  12.   length2 = rec[0][x][0]
  13.   length = length1 + 1 + length2
  14.   begin = rec[1][p][1]
  15.   end = rec[0][x][1]
  16.   del rec[0][x]
  17.   del rec[1][p]
  18.   rec[0][begin] = (length, end)
  19.   rec[1][end] = (length, begin)
  20.  
  21.  
  22. def growLeft(x, p, rec):
  23.   length = 1 + rec[0][x][0]
  24.   end = rec[0][x][1]
  25.   del rec[0][x]
  26.   rec[0][p] = (length, end)
  27.   rec[1][end] = (length, p)
  28.  
  29.  
  30. def growRight(x, p, rec):
  31.   length = rec[1][p][0] + 1
  32.   begin = rec[1][p][1]
  33.   del rec[1][p]
  34.   rec[0][begin] = (length, x)
  35.   rec[1][x] = (length, begin)
  36.  
  37.  
  38. def insert(x, p, rec):
  39.   rec[0][p] = (1, x)
  40.   rec[1][x] = (1, p)
  41.  
  42.  
  43. def update(x, p, d):
  44.   if d not in subseqs:
  45.     heapq.heappush(heap, d)
  46.     subseqs[d] = ({},{})
  47.  
  48.   rec = subseqs[d]
  49.  
  50.   if x in rec[0]:
  51.     if p in rec[1]:
  52.       merge(x, p, rec)
  53.     else:
  54.       growLeft(x, p, rec)
  55.   else:
  56.     if p in rec[1]:
  57.       growRight(x, p, rec)
  58.     else:
  59.       insert(x, p, rec)
  60.  
  61.  
  62. def init(src):
  63.   prevElem.insert(0, None)
  64.  
  65.   for i in xrange(1, len(src)):
  66.     prevElem.insert(i, i-1)
  67.     d = src[i] - src[i-1]
  68.     update(i, i-1, d)
  69.  
  70.  
  71. def chooseTheBest(d):
  72.   global bestL
  73.   l = max(list(zip(*subseqs[d][0].values()))[0])
  74.   bestL = max(bestL, l)
  75.  
  76.  
  77. def updateIndexes(src, rec):
  78.   for end in rec[1].keys():
  79.     l = rec[1][end][0]
  80.     i = end
  81.  
  82.     for n in xrange(l):
  83.       link = prevElem[i]
  84.  
  85.       if link != 0:
  86.         prevElem[i] -= 1
  87.         d = src[i] - src[prevElem[i]]
  88.         update(i, prevElem[i], d)
  89.         i = link
  90.  
  91.  
  92. def findLESS(src):
  93.   global bestL
  94.   init(src)
  95.  
  96.   while len(heap) > 0:
  97.     d = heapq.heappop(heap)
  98.     chooseTheBest(d)
  99.     updateIndexes(src, subseqs[d])
  100.     del subseqs[d]
  101.  
  102.     if bestL * d > s[-1] - s[0]:
  103.       break
  104.  
  105.   return bestL
  106.  
  107.  
  108. a = [random.randint(0,40000) for r in xrange(28000)]
  109. s = sorted(list(set(a)))
  110.  
  111. print(findLESS(s) + 1)
  112.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/bW8meY
language:
Python (cpython 2.7.16)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!