【在线编程产品介绍】
阿里云开发者社区在线编程：
免费刷题大神器，助你拿到好offer
周赛月赛不停歇，做题还能领奖品
大赛笔试全真题，常做常新有惊喜
点击链接开始产品体验：https://developer.aliyun.com/coding
本文为大家介绍的是“122.Codancer的数组封印”的解法探究。先来看一下题目内容：
题目详情
等级：困难
知识点：DP、LIS
查看题目：Codancer的数组封印
Tom有一个长度为n的排列数组a，即a中的每个数字的范围都在[1,n]中并且每个数字都不重复。但是现在Codancer把整个数组给封印了！
现在Codancer给了Tom一个解封序列b,即bi代表第i次解封a[b[i]]。
接下来Tom每次都会解封一个位置的数字，令L[i]代表第i次解封后所有被解封的数字构成的数组的LIS的长度，现在Codancer想让Tom计算L[1]+L[2]+L[3]+…+L[n]的值是多少？
第一行是一个正整数n，代表a数组和b数组的长度，接下来第一行输入数组a，第二行输入数组b。(1<=n<=50000)
输出L[1]+L[2]+…+L[n]的值。
示例1
输入：
4
[4,2,1,3]
[1,2,4,3]
输出：
6
注意
L[1]=1 解封后为{4}
L[2]=1 解封后为{4,2}
L[3]=2 解封后为{4,2,3}
L[4]=2 解封后为{4,2,1,3}
解题方法：
第一步解封后数组为{4}，因此L[1]=1
第二步解封后数组为{4,2}，因此L[2]=1
第三步解封后数组为{4,2,3}，因此L[3]=2
第四步解封后数组为{4,2,1,3}，因此L[4]=2
因此L[1]+L[2]+L[3]+L[4]=6
红色数字构成的序列即为LIS。
我们逆向思考，对于给定的数组每次删去一个数，相邻两次操作的答案不会超过1，
对于第i次操作我们随便求一个LIS,如果第i+1次操作删除的数字在这个LIS内，
我们就要重新求LIS,否则答案保持不变，由于随机生成的全排列LIS长度的期望为sqrt(n)，因此最多计算sqrt(n)次LIS。
时间复杂度：O(nsqrt(n)*log(n))。
看完之后是不是有了答题思路了呢，快来练练手吧：122.Codancer的数组封印
在线编程周赛、月赛火热进行中，更有限时答题活动，定制卫衣、双肩背包、机械键盘等多重好礼等你来拿~每天都有好礼相送~点击了解周赛详情：在线编程3月份比赛正式开启！机械键盘等你拿！
