import sys
import copy
#Binary search
def binary(s, num):
#print "in binary s:" + str(s)
#print "in binary num:" + str(num)
l = len(s)
mid = l/2
#print "in binary s:" + str(s)
#print "in binary num:" + str(num)
#print "s[mid]:" + str(s[mid])
if((l!=0) and (l == 1)):
if(s[mid] < num):
return s[mid]
if((l!=0) and (l != 1)):
if ((s[mid] >= num) and (s[mid - 1 ] < num)):
return s[mid - 1]
elif ((s[mid] > num) and (s[mid - 1] > num)):
return binary(s[:mid -1] , num)
else:
return binary(s[mid:], num)
t = int(raw_input())
for p in xrange(0,t):
n = int(raw_input())
arr = map(int, raw_input().split())
#maxlen in worst case would be 1 and end element index is 0.
maxlen = 1
bestend = 0
s = []
LIS = []
s.append(arr[bestend])
LIS.append(s)
#LIS[-1].append(s)
#print s
#print LIS
#To get last elements of all lists
#print max(LIS, key=len)[-1]
# to get the last element of the max length in the list
for i in xrange(1,n):
#print "arr[i]:" + str(arr[i])
#print "list end element to compare:" + str(max(LIS, key=len)[-1])
if(arr[i] > max(LIS, key=len)[-1]):
seq = copy.deepcopy(LIS)
max(seq, key=len).append(arr[i])
LIS.append(max(seq, key=len))
#print "post updated LIS:" + str(LIS)
else:
seq = copy.deepcopy(LIS)
last_elem = [x[-1] for x in seq]
val_greater_elem = binary(sorted(last_elem), arr[i])
if val_greater_elem in last_elem:
ind = last_elem.index(val_greater_elem)
#print "Index of ele:" + str(ind)# to get index of the ele to append
#print "seq ind to append:" + str(seq[ind][-1])
seq[ind].append(arr[i])#replace element
#print "updated seq:" + str(seq)
#print "updated seq index:" + str(seq[ind])
#print "Length of seq:" + str(len(seq[ind]))
len_of_updated = len(seq[ind])
k = [x for x in LIS if (len(x) == len_of_updated)]
[LIS.remove(l) for l in k]
#print "post discard LIS:" + str(LIS)
LIS.append(seq[ind])
#print "post updated LIS:" + str(LIS)
print len(max(LIS, key=len))
print "Final subseq:" + str(max(LIS, key=len))
stdin:
1
16
0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15
Output:
6
Final subseq: [0 2 6 9 11 15]
