<s> """<STR_LIT>""" <EOL> def longest_increasing_subsequence ( nums ) : <EOL> cache = [ <NUM_LIT:1> ] * len ( nums ) <EOL> location = [ - <NUM_LIT:1> ] * len ( nums ) <EOL> for i in range ( <NUM_LIT:1> , len ( nums ) ) : <EOL> for j in range ( <NUM_LIT:0> , i ) : <EOL> if nums [ i ] > nums [ j ] : <EOL> if cache [ j ] + <NUM_LIT:1> > cache [ i ] : <EOL> cache [ i ] = cache [ j ] + <NUM_LIT:1> <EOL> location [ i ] = j <EOL> max_value = max ( cache ) <EOL> solution = [ ] <EOL> i = cache . index ( max_value ) <EOL> while location [ i ] > - <NUM_LIT:1> : <EOL> solution . append ( nums [ i ] ) <EOL> i = location [ i ] <EOL> solution . append ( nums [ i ] ) <EOL> return max_value , solution [ : : - <NUM_LIT:1> ] <EOL> if __name__ == "<STR_LIT:__main__>" : <EOL> assert longest_increasing_subsequence ( [ <NUM_LIT:3> , <NUM_LIT:4> , - <NUM_LIT:1> , <NUM_LIT:0> , <NUM_LIT:6> , <NUM_LIT:2> , <NUM_LIT:3> ] ) == ( <NUM_LIT:4> , [ - <NUM_LIT:1> , <NUM_LIT:0> , <NUM_LIT:2> , <NUM_LIT:3> ] ) <EOL> assert longest_increasing_subsequence ( [ <NUM_LIT:10> , <NUM_LIT> , <NUM_LIT:9> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT:50> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> ] ) == ( <NUM_LIT:6> , [ <NUM_LIT:10> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT:50> , <NUM_LIT> , <NUM_LIT> ] ) <EOL> assert longest_increasing_subsequence ( [ <NUM_LIT:5> , <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:3> , <NUM_LIT:4> , <NUM_LIT:5> , <NUM_LIT:6> , <NUM_LIT:7> , <NUM_LIT:8> , <NUM_LIT:9> , <NUM_LIT:10> , <NUM_LIT:11> , <NUM_LIT:12> , <NUM_LIT:2> , <NUM_LIT:8> , <NUM_LIT:10> , <NUM_LIT:3> , <NUM_LIT:6> , <NUM_LIT:9> , <NUM_LIT:7> ] ) == ( <NUM_LIT> , [ <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:3> , <NUM_LIT:4> , <NUM_LIT:5> , <NUM_LIT:6> , <NUM_LIT:7> , <NUM_LIT:8> , <NUM_LIT:9> , <NUM_LIT:10> , <NUM_LIT:11> , <NUM_LIT:12> ] ) </s>
