-
Notifications
You must be signed in to change notification settings - Fork 0
/
lgis.py
52 lines (44 loc) · 1.23 KB
/
lgis.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# @File : lgis.py
# @Date : 2019-02-18
# @Author : luyang([email protected])
def lis(arr):
n = len(arr)
m = [0] * n
for x in range(n - 2, -1, -1):
for y in range(n - 1, x, -1):
if arr[x] < arr[y] and m[x] <= m[y]:
m[x] += 1
max_value = max(m)
result = []
for i in range(n):
if m[i] == max_value:
result.append(arr[i])
max_value -= 1
return result
def lds(arr):
n = len(arr)
m = [0] * n
for x in range(n - 2, -1, -1):
for y in range(n - 1, x, -1):
if arr[x] > arr[y] and m[x] <= m[y]:
m[x] += 1
max_value = max(m)
result = []
for i in range(n):
if m[i] == max_value:
result.append(arr[i])
max_value -= 1
return result
def main():
file = 'input/rosalind_lgis.txt'
with open(file) as f:
n = int(f.readline())
numbers = list(map(int, f.readline().strip().split()))
lis_seq = lis(numbers)
print(' '.join(map(str, lis_seq)))
lds_seq = lds((numbers))
print(' '.join(map(str, lds_seq)))
if __name__ == "__main__":
main()