Bioinformatics-Python-Scripts/longestIncreasing at master · esmason/Bioinformatics-Python-Scripts · GitHub

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
import math

file = open('dna7.txt')

read = file.read()

file = read

test = file.replace('\n', ',')

test = test.split(' ')

inarray = [int(x.replace(',', '')) for x in test]

inarray = list(reversed(inarray))
P = [None for i in range(len(inarray))]
M = [None for i in range(len(inarray) + 1)]

L=0
for i in range(len(inarray)):
    lo = 1
    hi = L
    while lo <= hi:
        mid = math.ceil((lo+hi)/2)
        #print(M)
        if inarray[M[mid]] <= inarray[i]:
            lo = mid + 1
        else:
            hi = mid - 1
    newL = lo

    P[i] = M[newL - 1]
    M[newL] = i

    if newL > L:
        L = newL

S = [None for i in range(L)]
k = M[L]
for i in reversed(range(L)):
    S[i] = inarray[k]
    k = P[k]

for s in reversed(S):
    print(s, end = '')
    print(' ', end = '')

print('')