允许K个例外的最长递增子序列 [英] Longest increasing subsequence with K exceptions allowed

问题描述

你好，我坚持做我的作业:给定整数序列，找到元素按升序排列的最长子序列.最多k个异常意味着最多k次，序列中的下一个数字小于前一个.输出应该是最长的子序列的长度.

Hello I am stuck with my homework which is: given sequence of integers, find the longest subsequence whose elements are ordered in an increasing order. Up to k exceptions that means at most k times, the next number in the sequence is smaller than previous one. Output should be the length of the longest such subsequence.

我发现了很多找到LIS的例子，甚至有一个允许更改一次，但是我不知道如何检查k个更改.这是发布更改的链接: https ://www.geeksforgeeks.org/longest-increasing-subarray-with-one-change-allowed/amp/

I found many examples of finding LIS, even one with one change allowed, but I don't know how to check with k changes. Here is the link to post with one change: https://www.geeksforgeeks.org/longest-increasing-subarray-with-one-change-allowed/amp/

推荐答案

您可以设置k个计数器并遍历序列.一旦遇到异常，您将转到下一个柜台.如果到达第k + 1个计数器，则删除第一个计数器，然后将所有计数器移位一个，以使第n + 1个计数器变为第n个计数器.在每一步中，您都将当前索引与k个计数器的总和一起存储为总序列长度.最后取最大的

You can set up k counters and traverse the sequence. Once you reach an exception you go to the next counter. If you reached the k+1-th counter you drop the first one and shift all your counters by one so that the n+1th counter becomes the nth. With each step you store the current index together with the sum of your k counters as the total sequence length. Take the maximum of that in the end

说明: 问题仅是最长子序列从何处开始.如果您知道该异常有多长时间(直到k + 1)或该序列的末尾).让这一点成为s. 最长的子序列只能在异常或序列开始时开始.如果不是，您可以将s-1项添加到序列中，而无需添加例外，并形成更长的子序列. 上面的方法会计算所有可能的最长子序列，并最终选择最长的候选者.

Explanation: The question is only where the longest subsequence begins. If you know that you know how long it is (until the k+1) exception or the end of the sequence). Let this point be s. The longest subsequence can only begin at an exception or at the start of the sequence. If not you could add the s-1 item to the sequence without adding an exception and form a longer subsequence. The method above computes all possible longest subsequences and chooses the longest candidate in the end.

这篇关于允许K个例外的最长递增子序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！