Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
45 lines (38 sloc) 810 Bytes
#!/usr/bin/python
import numpy as np
with open("rosalind_lgis.txt","rU") as f:
n=f.readline()
nums=f.read()
num_list=nums.strip().split()
nums=np.array([int(x) for x in num_list])
def lis(nums):
N=len(nums)
DP=np.ones(N)
prev=np.empty(N)
prev.fill(-1)
isave=0
DPsave=0
for i in range(N):
for j in range(i):
if DP[j]+1>DP[i] and nums[i]>nums[j]:
DP[i]+=1
prev[i]=j
if DP[i]>DPsave:
isave=i
DPsave=DP[i]
seq=[]
j=isave
while prev[j]!=-1:
seq.insert(0,nums[j])
j=prev[j]
seq.insert(0,nums[j])
return(np.array(seq))
ans=lis(nums)
for x in ans:
print x,
print
rnums=-nums
ans=-lis(rnums)
for x in ans:
print x,
print
You can’t perform that action at this time.