Longest Increasing Sequence using python

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]