The problem here is to find the length of longest subsequence from the input array such that all the elements are in sorted order.
Example: input => [10,22,9,33,21,50,41,60,80]
Example: Output => [10,22,33,50,60,80] is 6
My attempt:
def longest_sequence(input):
obj = []
for x in sorted(input):
obj.append(x)
print[obj, len(obj)]
# [[9, 10, 21, 22, 33, 41, 50, 60, 80], 9]
longest_sequence([10,22,9,33,21,50,41,60,80])
import bisect
def lis(xs):
ret = []
for x in xs:
i = bisect.bisect_left(ret, x)
ret[i:i+1] = x,
return len(ret)
Example:
>>> lis([10, 1, 2, 3])
3
>>> lis([10,22,9,33,21,50,41,60,80])
6
NOTE In the above code,ret does not contains valid subsequence. But the length is correct. Use the above code what you want is only the length of the LIS.
Explanation:
Think about [10,22,9,11]. There could be two LIS: [10,22], [9,11]. The ret in the above lis function maintains the following condition:
ret is sorted; can use binary search (bisect.bisect_left)ret[i] contains the minimum last value for length-i subsequence.ret changes as... (given [10,22,9,11] as input)
Time complexity: O(nk) where n is the number of list item, k is the length of the LIS.
UPDATE
Modified version that correctly get the subsequence:
import bisect
def lis(xs):
if not xs: return []
prev = {}
ret = []
for x in xs:
i = bisect.bisect_left(ret, x)
ret[i:i+1] = x,
prev[x] = ret[i-1] if i > 0 else None
subseq = [ret[-1]]
while subseq[-1] is not None:
subseq.append(prev[subseq[-1]])
return list(reversed(subseq[:-1]))
Example:
>>> lis([])
[]
>>> lis([10, 1, 2, 3])
[1, 2, 3]
>>> lis([10,22,9,33,21,50,41,60,80])
[10, 22, 33, 41, 60, 80]
>>> lis([1,5,2,6,3,4])
[1, 2, 3, 4]
>>> lis([100,200,1,2,3])
[1, 2, 3]
data = [100,1,2,3]
conformed = []
for i in range (0, len(data)):
if i == 0:
if data[1]<data[0]:
conformed.append(data[1])
else:
conformed.append(data[0])
else:
if data[i] > data[i-1]:
conformed.append(data[i])
print conformed, len(conformed)
