<s> class Solution ( object ) : <EOL> def lengthOfLIS ( self , nums ) : <EOL> """<STR_LIT>""" <EOL> LIS = [ ] <EOL> def insert ( target ) : <EOL> left , right = <NUM_LIT:0> , len ( LIS ) - <NUM_LIT:1> <EOL> while left <= right : <EOL> mid = left + ( right - left ) / <NUM_LIT:2> ; <EOL> if LIS [ mid ] >= target : <EOL> right = mid - <NUM_LIT:1> <EOL> else : <EOL> left = mid + <NUM_LIT:1> <EOL> if left == len ( LIS ) : <EOL> LIS . append ( target ) ; <EOL> else : <EOL> LIS [ left ] = target <EOL> for num in nums : <EOL> insert ( num ) <EOL> return len ( LIS ) <EOL> class Solution2 ( object ) : <EOL> def lengthOfLIS ( self , nums ) : <EOL> """<STR_LIT>""" <EOL> dp = [ ] <EOL> for i in xrange ( len ( nums ) ) : <EOL> dp . append ( <NUM_LIT:1> ) <EOL> for j in xrange ( i ) : <EOL> if nums [ j ] < nums [ i ] : <EOL> dp [ i ] = max ( dp [ i ] , dp [ j ] + <NUM_LIT:1> ) <EOL> return max ( dp ) if dp else <NUM_LIT:0> </s>
