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