Longest increasing subsequence with K exceptions allowed

1
votes

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.

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/

1
subsequence
Hi, welcome to StackOverflow. In order to get your question answered, please create a minimal reproducible example – rpm192
what you tried? what is your code so far? are there any errors? or result is not full? – Lukas Novicky
See stackoverflow.com/q/59474521/781723 and cs.stackexchange.com/q/118858/755 for solutions. – D.W.
Does this answer your question? Longest K Sequential Increasing Subsequences – D.W.

1 Answers

0
votes

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

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.