<s> import bisect <EOL> from functools import partial , reduce <EOL> maximum = partial ( reduce , max ) <EOL> def patience_sort ( xs ) : <EOL> '''<STR_LIT>''' <EOL> pile_tops = list ( ) <EOL> for x in xs : <EOL> pile = bisect . bisect_left ( pile_tops , x ) <EOL> if pile == len ( pile_tops ) : <EOL> pile_tops . append ( x ) <EOL> else : <EOL> pile_tops [ pile ] = x <EOL> yield x , pile <EOL> def longest_monotonic_subseq_length ( xs ) : <EOL> '''<STR_LIT>''' <EOL> li = longest_increasing_subseq_length ( xs ) <EOL> ld = longest_decreasing_subseq_length ( xs ) <EOL> return max ( li , ld ) , li - ld <EOL> def longest_increasing_subseq_length ( xs ) : <EOL> '''<STR_LIT>''' <EOL> return <NUM_LIT:1> + maximum ( ( pile for x , pile in patience_sort ( xs ) ) , - <NUM_LIT:1> ) <EOL> def longest_decreasing_subseq_length ( xs ) : <EOL> return longest_increasing_subseq_length ( reversed ( xs ) ) <EOL> def longest_monotonic_subseq_length_loose ( xs ) : <EOL> li = longest_increasing_subseq_length_loose ( xs ) <EOL> ld = longest_decreasing_subseq_length_loose ( xs ) <EOL> return max ( li , ld ) , li - ld <EOL> def longest_increasing_subseq_length_loose ( xs ) : <EOL> xs = [ ( x , i ) for ( i , x ) in enumerate ( xs ) ] <EOL> return longest_increasing_subseq_length ( xs ) <EOL> def longest_decreasing_subseq_length_loose ( xs ) : <EOL> xs = [ ( x , - i ) for ( i , x ) in enumerate ( xs ) ] <EOL> return longest_decreasing_subseq_length ( xs ) <EOL> def longest_increasing_subsequence ( xs ) : <EOL> '''<STR_LIT>''' <EOL> piles = [ [ ] ] <EOL> for x , p in patience_sort ( xs ) : <EOL> if p + <NUM_LIT:1> == len ( piles ) : <EOL> piles . append ( [ ] ) <EOL> piles [ p + <NUM_LIT:1> ] . append ( ( x , len ( piles [ p ] ) - <NUM_LIT:1> ) ) <EOL> npiles = len ( piles ) - <NUM_LIT:1> <EOL> prev = <NUM_LIT:0> <EOL> lis = list ( ) <EOL> for pile in range ( npiles , <NUM_LIT:0> , - <NUM_LIT:1> ) : <EOL> x , prev = piles [ pile ] [ prev ] <EOL> lis . append ( x ) <EOL> lis . reverse ( ) <EOL> return lis <EOL> def longest_decreasing_subsequence ( xs ) : <EOL> '''<STR_LIT>''' <EOL> return list ( reversed ( longest_increasing_subsequence ( reversed ( xs ) ) ) ) <EOL> def longest_monotonic_subsequence ( xs ) : <EOL> lis = longest_increasing_subsequence ( xs ) <EOL> lds = longest_decreasing_subsequence ( xs ) <EOL> if len ( lis ) >= len ( lds ) : <EOL> return lis <EOL> return lds <EOL> def longest_monotonic_subsequence_loose ( xs ) : <EOL> lis = longest_increasing_subsequence_loose ( xs ) <EOL> lds = longest_decreasing_subsequence_loose ( xs ) <EOL> if len ( lis ) >= len ( lds ) : <EOL> return lis <EOL> return lds <EOL> def longest_increasing_subsequence_loose ( xs ) : <EOL> xs = [ ( x , i ) for ( i , x ) in enumerate ( xs ) ] <EOL> ll = longest_increasing_subsequence ( xs ) <EOL> return [ x for ( x , i ) in ll ] <EOL> def longest_decreasing_subsequence_loose ( xs ) : <EOL> xs = [ ( x , - i ) for ( i , x ) in enumerate ( xs ) ] <EOL> ll = longest_decreasing_subsequence ( xs ) <EOL> return [ x for ( x , i ) in ll ] <EOL> def backtracking ( a , L , bestsofar ) : <EOL> """<STR_LIT>""" <EOL> w , j = max ( L . items ( ) ) <EOL> while j != - <NUM_LIT:1> : <EOL> yield j <EOL> w , j = bestsofar [ j ] <EOL> def heaviest_increasing_subsequence ( a , debug = False ) : <EOL> """<STR_LIT>""" <EOL> L = { <NUM_LIT:0> : - <NUM_LIT:1> } <EOL> bestsofar = [ ( <NUM_LIT:0> , - <NUM_LIT:1> ) ] * len ( a ) <EOL> for i , ( key , weight ) in enumerate ( a ) : <EOL> for w , j in L . items ( ) : <EOL> if j != - <NUM_LIT:1> and a [ j ] [ <NUM_LIT:0> ] >= key : <EOL> continue <EOL> new_weight = w + weight <EOL> if new_weight in L and a [ L [ new_weight ] ] [ <NUM_LIT:0> ] <= key : <EOL> continue <EOL> L [ new_weight ] = i <EOL> newbest = ( new_weight , j ) <EOL> if newbest > bestsofar [ i ] : <EOL> bestsofar [ i ] = newbest <EOL> if debug : <EOL> print ( key , weight ) , bestsofar <EOL> tb = reversed ( list ( backtracking ( a , L , bestsofar ) ) ) <EOL> return [ a [ x ] for x in tb ] , max ( L . items ( ) ) [ <NUM_LIT:0> ] <EOL> if __name__ == '<STR_LIT:__main__>' : <EOL> import doctest <EOL> doctest . testmod ( ) <EOL> import numpy as np <EOL> A = np . random . random_integers ( <NUM_LIT:0> , <NUM_LIT:10> , <NUM_LIT:10> ) <EOL> A = list ( A ) <EOL> B = zip ( A , [ <NUM_LIT:1> ] * <NUM_LIT:10> ) <EOL> print A <EOL> lis = longest_increasing_subsequence ( A ) <EOL> print "<STR_LIT>" , lis <EOL> lds = longest_decreasing_subsequence ( A ) <EOL> print "<STR_LIT>" , lds <EOL> lisl = longest_increasing_subsequence_loose ( A ) <EOL> print "<STR_LIT>" , lisl <EOL> ldsl = longest_decreasing_subsequence_loose ( A ) <EOL> print "<STR_LIT>" , ldsl <EOL> his , his_dd = heaviest_increasing_subsequence ( B ) <EOL> hlis , wts = zip ( * his ) <EOL> print "<STR_LIT>" , hlis <EOL> assert len ( lis ) == len ( his ) </s>
