(sequence)
return ans
Optimized dynamic programming algorithm for
    counting the length of the longest increasing subsequence
    using segment tree data structure to achieve better complexity
    type sequence: list[int]
    rtype: int
Optimized dynamic programming algorithm for
    counting the length of the longest increasing subsequence
    using segment tree data structure to achieve better complexity
    type sequence: list[int]
    rtype: int
Optimized dynamic programming algorithm for counting the length of the longest increasing subsequence using segment tree data structure to achieve better complexity type sequence : list [ int ] rtype : int
def longest_increasing_subsequence_optimized2(sequence):
    """
    Optimized dynamic programming algorithm for
    counting the length of the longest increasing subsequence
    using segment tree data structure to achieve better complexity
    type sequence: list[int]
    rtype: int
    """
    n = len(sequence)
    tree = [0] * (n<<2)
    sorted_seq = sorted((x, -i) for i, x in enumerate(sequence))
    def update(p, l, r, i, v):
        if l ==r:
            tree[p] = v
            return
        mid = (l+r)>>1
        if i <= mid:
            update(p<<1, l, mid, i, v)
        else:
            update((p<<1)|1, mid+1, r, i, v)
        tree[p] = max(tree[p<<1], tree[(p<<1)|1])

    def get_max(p, l, r, s, e):
        if l > e or r < s:
            return 0
        if l >= s and r <= e:
            return tree[p]
        mid = (l+r)>>1
        return max(get_max(p<<1, l, mid, s, e), get_max((p<<1)|1, mid+1, r, s, e))
    ans = 0
    for x, j in sorted_seq:
        i = -j
        cur = get_max(1, 0, n-1, 0, i-1)+1
        ans = max(ans, cur)
        update(1, 0, n-1, i, cur)
    return ans
def longest_increasing_subsequence_optimized2 ( sequence ) : n = len ( sequence ) tree = [ 0 ] * ( n << 2 ) sorted_seq = sorted ( ( x , - i ) for i , x in enumerate ( sequence ) ) def update ( p , l , r , i , v ) : if l == r : tree [ p ] = v return mid = ( l + r ) >> 1 if i <= mid : update ( p << 1 , l , mid , i , v ) else : update ( ( p << 1 ) | 1 , mid + 1 , r , i , v ) tree [ p ] = max ( tree [ p << 1 ] , tree [ ( p << 1 ) | 1 ] ) def get_max ( p , l , r , s , e ) : if l > e or r < s : return 0 if l >= s and r <= e : return tree [ p ] mid = ( l + r ) >> 1 return max ( get_max ( p << 1 , l , mid , s , e ) , get_max ( ( p << 1 ) | 1 , mid + 1 , r , s , e ) ) ans = 0 for x , j in sorted_seq : i = - j cur = get_max ( 1 , 0 , n - 1 , 0 , i - 1 ) + 1 ans = max ( ans , cur ) update ( 1 , 0 , n - 1 , i , cur ) return ans