Title Description
Redraiment He is a master of plum blossom pile .Redraiment You can choose any starting point , From before to after , But you can only go from the low to the high pile . He wants to take the most steps , Can you do it for me Redraiment Study the most steps he takes ？
This question contains several groups of sample input
Input description :
Enter multiple sets of data ,1 Group has 2 That's ok , The first 1 First enter the number of arrays in the row , The first 2 Row and then enter the height of the plum blossom pile
Output description :
One group outputs one result
Example 1
Input
6
2 5 1 5 4 5
3
3 2 1
Output
3
1
explain
6 The height of each point is 2 5 1 5 4 5
For example, from the first 1 Greg began to walk , At most 3 Step , 2 4 5
From 2 Greg began to walk , Only up to 1 Step ,5
And from the beginning 3 Greg started walking, up to 3 Step ,1 4 5
From 5 Greg started walking, up to 2 Step ,4 5
So the result is 3.
Code implementation ：
import bisect
def func():
while True:
try:
a = input()
b = list(map(int,input().split()))
lists = []
for i in b:
## stay list Search for x,x Return when there is x Left position ,x There is no return to the position that should be inserted
k = bisect.bisect_left(lists, i)
#print(k,i,lists)
if k == len(lists):
lists.append(i)
else:
lists[k] = i
#print(lists)
print(len(lists))
except Exception as e:
#print(e)
break
if __name__ == '__main__':
func()
expand ：
https://docs.python.org/zh-cn/2/library/bisect.html
