39 "def longest_monotone(seq, allow_same=False, debug=False):\n",
40 " \"\"\"Find the longest monotonic substring. If allow_same is True, \n",
41 " instead find the longest non-decreasing or non-increasing substring\"\"\"\n",
42 " cmps = [cmp(x, y) for x, y in zip(seq, seq[1:])]\n",
43 " groups = [(k, len(list(g)) + 1) for k, g in itertools.groupby(cmps)]\n",
45 " groups = merged(groups)\n",
47 " return max(t[1] for t in groups), groups\n",
49 " return max(t[1] for t in groups)"
61 " padded = gs + [(0, 0)]\n",
64 " for curr, nxt in zip(padded, padded[1:]):\n",
65 " if prev[0] == 0:\n",
66 " prev = (curr[0], prev[1] + curr[1] - 1)\n",
67 " elif curr[0] == 0:\n",
68 " prev = (prev[0], prev[1] + curr[1] - 1)\n",
69 " if prev[0] != nxt[0]:\n",
71 " prev = (0, curr[1])\n",
72 " elif prev[0] == curr[0]:\n",
73 " prev = (prev[0], prev[1] + curr[1] - 1)\n",
96 "output_type": "execute_result"
100 "longest_monotone([1,2,3,4,5,4,5,6])"
105 "execution_count": 6,
113 "(5, [(1, 5), (-1, 2), (1, 3)])"
116 "execution_count": 6,
118 "output_type": "execute_result"
122 "longest_monotone([1,2,3,4,5,4,5,6], debug=True)"
127 "execution_count": 7,
138 "execution_count": 7,
140 "output_type": "execute_result"
144 "longest_monotone([10,1,2,3,4,5,4,5,6])"
149 "execution_count": 8,
160 "execution_count": 8,
162 "output_type": "execute_result"
166 "longest_monotone([10,1,2,3,4,5,5,5,4,3,5,6])"
171 "execution_count": 9,
182 "execution_count": 9,
184 "output_type": "execute_result"
188 "longest_monotone([10,1,2,3,4,5,5,5,4,3,5,6], allow_same=True)"
193 "execution_count": 10,
204 "execution_count": 10,
206 "output_type": "execute_result"
210 "longest_monotone([10,1,2,5,5,5,4,3,2,1,5,6])"
215 "execution_count": 11,
226 "execution_count": 11,
228 "output_type": "execute_result"
232 "longest_monotone([10,1,2,5,5,5,4,3,2,1,5,6], allow_same=True)"
237 "execution_count": 12,
248 "execution_count": 12,
250 "output_type": "execute_result"
254 "longest_monotone([10,1,2,5,5,5,4,3,2,5,6,6,6,6,6,6,6,2])"
259 "execution_count": 13,
270 "execution_count": 13,
272 "output_type": "execute_result"
276 "longest_monotone([10,1,2,5,5,5,4,3,2,5,6,6,6,6,6,6,6,2], allow_same=True)"
281 "execution_count": 14,
292 "execution_count": 14,
294 "output_type": "execute_result"
298 "longest_monotone([10,1,2,5,5,5,6,7,7,8,8,3,2,5,6,6,6,6,6,6,6,2], allow_same=False)"
303 "execution_count": 15,
314 "execution_count": 15,
316 "output_type": "execute_result"
320 "longest_monotone([10,1,2,5,5,5,6,7,7,8,8,3,2,5,6,6,6,6,6,6,6,2], allow_same=True)"
325 "execution_count": 16,
332 "output_type": "stream",
339 "for i in range(1):\n",
340 " with open('sequence{:03}.txt'.format(i)) as f:\n",
341 " sseq = f.read()\n",
342 " seq = [int(s) for s in sseq.split(',')]\n",
343 " s = longest_monotone(seq)\n",
349 "execution_count": 17,
356 "output_type": "stream",
372 "for i in range(10):\n",
373 " with open('sequence{:03}.txt'.format(i)) as f:\n",
374 " sseq = f.read()\n",
375 " seq = [int(s) for s in sseq.split(',')]\n",
376 " s = longest_monotone(seq)\n",
382 "execution_count": 18,
389 "output_type": "stream",
405 "for i in range(10):\n",
406 " with open('sequence{:03}.txt'.format(i)) as f:\n",
407 " sseq = f.read()\n",
408 " seq = [int(s) for s in sseq.split(',')]\n",
409 " s = longest_monotone(seq, allow_same=True)\n",
415 "execution_count": null,
425 "display_name": "Python 3",
426 "language": "python",
434 "file_extension": ".py",
435 "mimetype": "text/x-python",
437 "nbconvert_exporter": "python",
438 "pygments_lexer": "ipython3",