Pocket Gems Engineering challenge

LIS.py

import random

def lis(a):
    # a is list of tuples of form (sat, gpa)
    # to find LIS such that sat1<sat2<sat3....
    # and gpa1>gpa2>gpa>3.....
    
    # sort the list in decreasing order of gpa
    a = sorted(a, reverse = True, key = lambda k: k[-1])
    
    # length of sequence
    n = len(a)
    
    # s[i] stores the length of LIS ending at data
    # initially it stores the value for each value
    s = [1 for i in xrange(n)]
    
    for j in xrange(n):
        for i in xrange(j+1,n):
            if a[j][0] < a[i][0] and s[j] + 1 > s[i]:
                s[i] = s[j] + 1
    
    max = -1
    posM = n+1
    
    for pos, val  in enumerate(s):
        if val > max:
            max = val
            posM = pos
    
    max = a[posM][0]
    
    res = []
    res.append(a[posM])
    
    for i in xrange(posM-1,-1,-1):
        if max > a[i][0] and s[posM] == s[i] + 1:
            max = a[i][0]
            posM = i
            res.append(a[i])
    
    res = res[::-1]
    
    return res
    
if __name__ == "__main__":
    
    data = []
    # assuming SAT values between 600 to 2400 and gpa between 2 and 5
    for i in xrange(1000):
        x = random.randint(600,2400)
        y = round(random.uniform(2,5),2)
        data.append((x,y))
    print lis(data)