# 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