Guest User

Untitled

a guest
Jul 13th, 2020
31
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import random
  2. data = [random.randint(0, 300) for _ in range(100000)]
  3. k = 30
  4.  
  5.  
  6.  
  7. class deque:
  8.     def __init__(self):
  9.         self.deque = []
  10.         self.f = 0
  11.     def push_back (self, n):
  12.         self.deque.append(n)
  13.         return self
  14.  
  15.     def push_front(self, n):
  16.         if (self.f):
  17.             self.f-= 1
  18.             self.deque[n]
  19.         else:
  20.             self.deque.insert(0, n)
  21.         return self
  22.  
  23.     def pop_back(self):
  24.         if self.size():
  25.             k = self.deque.pop(-1)
  26.         return self
  27.    
  28.     def pop_front(self):
  29.         if self.size():
  30.             self.f+= 1
  31.         return self
  32.  
  33.     def back(self):
  34.         if self.size():
  35.             return self.deque[-1]
  36.  
  37.     def front(self):
  38.         if self.size():
  39.             return self.deque[self.f]
  40.  
  41.     def size(self):
  42.         return len(self.deque) - self.f
  43.  
  44.  
  45. cache = [(0, -1)] * (len(data) + 2*k + 1)
  46. cacheMax = [-1] * len(cache)
  47. d = deque()
  48. for i in range(len(data) - 1, -1, -1):
  49.    
  50.     if i + k < len(cacheMax):
  51.         maxNext = cacheMax[i + k]
  52.         maxSum = cache[maxNext][0]
  53.     else:
  54.         maxNext = -1
  55.         maxSum = 0
  56.    
  57.     maxSum = maxSum + data[i]
  58.     cache[i] = (maxSum, maxNext)
  59.    
  60.     if i < len(cache)-k and d.front() == i + k:
  61.         d.pop_front()
  62.        
  63.     while d.size() and cache[d.back()] <= cache[i]:
  64.         d.pop_back()
  65.        
  66.     d.push_back(i)
  67.    
  68.     cacheMax[i] = d.front()
  69.    
  70. maxSum, maxStart = max(
  71.         map(
  72.                 lambda i: (cache[i][0], i),
  73.                 list(range(0, k))
  74.             ),
  75.         key = lambda v: v[0]
  76.     )
  77.  
  78. maxList = []
  79. now = maxStart
  80.  
  81. while True:
  82.     maxList.append(now)
  83.     next = cache[now][1]
  84.     if next < 0 or next > len(data):
  85.         break
  86.     now = next
  87.    
  88.    
  89. print(maxList[0:50]) #иначе ругается на слишком длинный вывод
RAW Paste Data