快手算法岗A卷笔试第三题

同。蹲个答案

应该不会溢出啊……生成的序列最长399998个元素

同，求大神解答😂

我还是感觉应该有啥数学规律😂

俺觉得不是溢出的问题，就算溢出小的case也可能通过啊，0%的那种一般我都怀疑是输入输出问题

用树状数组或者线段树做dp, O(nlgn)

这个题目不可能有数学规律吧，题目中的序列生成算法不就是伪随机数生成算法么。

可以把LCS转化成LIS做，具体可以参考https://www.nowcoder.com/discuss/388827?toCommentIpt=1，代码最后一行改成 int ans = -1; for(int i = 0; i < na; i++) ans = max(ans, max(dp[i][0], dp[i][1])); 应该就没有问题了…… 当然现在没法提交我也没办法保证没有细节上的错误就是……上面大佬说的树状数组应该就是类似于这个方法

可以考虑转化成最长上升子序列问题 B序列遍历的过程中 每个位置的权值就是A序列相同元素的位置 以这个权值做最长上升子列 有2个的话转移两次即可 可以用线段树维护dp数组达到nlogn

我尝试过转换成LIS问题，复杂度O(nlogn) ，但是在python下也还是时间超过@BiteTheDust