中级农民
- 积分
- 104
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2020-1-3
- 最后登录
- 1970-1-1
|
![]()
继续动态规划:
nlogn的解法解释:
首先dp数组的长度是LIS的长度,因为我们在数组后面加比dp数组都大的数。而替换前面更小的数,是因为小的数比大的数更可能形成一个更长的LIS,当然会破坏原来的LIS,所以dp数组返回的不保证是正确的LIS。
比如 10 9 2 5 3 7 101 18, dp的变化如下
dp= 10
dp= 9 (因为以9开头的lis比10开头的更大,而后面的数比9大会被加在后面)
dp= 2
dp= 2 5
dp= 2 3
dp= 2 3 7(其实2 5 7也是有效lis,但5换成3更可能组成长的lis, 若是2 5 4呢?)
dp= 2 3 7 101
dp= 2 3 7 18 |
|