iterate through array and find end index of LIS and its Size
for i in range ( 1 , n ) : NEW_LINE INDENT if A [ i ] - 1 not in hash : NEW_LINE INDENT hash [ A [ i ] - 1 ] = 0 NEW_LINE DEDENT hash [ A [ i ] ] = hash [ A [ i ] - 1 ] + 1 NEW_LINE if LIS_size < hash [ A [ i ] ] : NEW_LINE INDENT LIS_size = hash [ A [ i ] ] NEW_LINE LIS_index = A [ i ] NEW_LINE DEDENT DEDENT