题解 | #Redraiment的走法#
Redraiment的走法
https://www.nowcoder.com/practice/24e6243b9f0446b081b1d6d32f2aa3aa
# 这题的意思就是 往右找比自己大的,包括自己看看有多少个，找这样 一个 最大的个数。
# 就是 最长 升序 子序列 长度；
# 动态规划 和 二分法 都适合解答。
'''
二分思路: 思想：
原始数组为A, 建立一个辅助数组B, 变量end用来记录B数组末尾元素的下标
遍历A中的所有的元素 x = A[i]
如果x > B的末尾元素，则将x追加到B的末尾，end+=1
如果x < B的末尾元素，则利用二分查找 bisect_left(list,goal) ，寻找B中第一个大于x的元素，并用x进行替换 e.g. x= 4 B=[1,3,5,6] ==> B=[1,3,4,6]
遍历结束之后，B的长度则为最长递增子序列的长度
'''
# ````````````````````````````````````````````````````````````````````````````````
'''
动态规划法: 思想:
假设长度为n的数组 a0 a1 a2...an , 以 ai 元素结尾的最长递增子序列为 Li ，
则当 j<i<n 且 ai>aj ,遇到大的了就考虑修改 Li ，Li = max(Li, Lj + 1 ) ,由递推公式知道遍历方向从左到右, Li 的初始值为1。这里需要理解，为什么max()内部会有一个 Li ，因为即便是j 和 i 并不相邻， 随着j的增长， 每一次判断都会考虑 Li 是否需要修改；
注意： 递推公式的使用是有条件的，一定是当 遇到了 ai > aj 的情况才可能使用，因此并不是d的最大值一定发生在最后！！！ 因为 可能后面一截并没有遇到增长的 a。
'''
# 综上来看，二分法解决 最长升序子序列 太过于巧妙不容易想到，优先考虑用动态规划方法解决；
num = int(input())
values = input().strip().split(' ')
values = list(map(int,values))
# print(values)
d = [1]*num
for i in range(num):
for j in range(i+1):
if values[i] > values[j]:
d[i] = max(d[i],d[j]+1)
print(max(d))
