小编Erm*_*lai的帖子

为什么我创建了一个重复的线程

我在阅读了Longest increase subsequence with K exceptions allowed之后创建了这个线程。我意识到，谁问这个问题的人并没有真正理解这个问题，因为他指的是一个链接解决了“最长递增子阵列与一个变化允许”的问题。所以他得到的答案实际上与 LIS 问题无关。

问题描述

假设数组A 的长度为N。找出最长的递增子序列，允许有K 个例外。

示例
1) N=9 , K=1

A=[3,9,4,5,8,6,1,3,7]

答案：7

解释：

最长递增子序列是：3,4,5,8(或6),1(exception),3,7 -> total=7

2) N=11 , K=2

A=[5,6,4,7,3,9,2,5,1,8,7]

答案：8

到目前为止我所做的...

如果 K=1，则只允许一种例外情况。如果使用已知的计算O(NlogN) 中最长递增子序列的算法（单击此处查看此算法），那么我们可以为数组的每个元素计算从 A[0] 到 A[N-1] 的 LIS A. 我们将结果保存在大小为N的新数组L 中。查看示例 n.1，L 数组将是： L=[1,2,2,3,4,4,4,4,5]。