题解 | #最长上升子序列(二)#
最长上升子序列(二)
https://www.nowcoder.com/practice/4af96fa010c44638a7e112abf65f7237
* 很重要，必须要会
* eg:arr={1, 3, 6, 7, 9, 4, 10, 5, 6}
* --------0 1 2 3 4 5 6 7 8
* 初始时：end[0]=arr[0]=1,R=0(R可以认为是end有效的范围内的长度-1)
* 从下标为1开始遍历
* i=1
* 从0~0(即0~R)通过二分查找，从end数组中找到比arr[1]小的最右侧位置+1，明显是下标为1，更新值为end={1,3},R=1
* i=2
* 从0~1(即0~R)通过二分查找，从end数组中找到比arr[2]小的最右侧位置+1，明显是下标为2，更新值为end={1,3,6},R=2
* i=3
* 从0~2(即0~R)通过二分查找，从end数组中找到比arr[3]小的最右侧位置+1，明显是下标为3，更新值为end={1,3,6,7},R=3
* i=4
* 从0~3(即0~R)通过二分查找，从end数组中找到比arr[4]小的最右侧位置+1，明显是下标为4，更新值为end={1,3,6,7,9},R=4
* i=5
* 从0~4(即0~R)通过二分查找，从end数组中找到比arr[5]=4小的最右侧位置+1，明显是下标为3，更新值为end={1,3,4,7,9},R=4
* i=6
* 从0~4(即0~R)通过二分查找，从end数组中找到比arr[6]=10小的最右侧位置+1，明显是下标为5，更新值为end={1,3,4,7,9,10},R=5
* i=7
* 从0~5(即0~R)通过二分查找，从end数组中找到比arr[7]=5小的最右侧位置+1，明显是下标为3，更新值为end={1,3,4,5,9,10},R=5
* i=8
* 从0~5(即0~R)通过二分查找，从end数组中找到比arr[8]=6小的最右侧位置+1，明显是下标为4，更新值为end={1,3,4,5,6,10},R=5
* 那么答案就是 R+1;