1

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/

Tyler Marshall
  • 489
  • 3
  • 9
KarmaL
  • 11
  • 3
  • 1
    Hi, welcome to StackOverflow. In order to get your question answered, please create a [mcve] – rpm192 May 15 '19 at 20:10
  • what you tried? what is your code so far? are there any errors? or result is not full? – Lukas Novicky May 15 '19 at 20:43
  • See https://stackoverflow.com/q/59474521/781723 and https://cs.stackexchange.com/q/118858/755 for solutions. – D.W. Jan 02 '20 at 19:01
  • Does this answer your question? [Longest K Sequential Increasing Subsequences](https://stackoverflow.com/questions/59474521/longest-k-sequential-increasing-subsequences) – D.W. Jan 02 '20 at 19:01

1 Answers1

0

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.

Raphael
  • 1,731
  • 2
  • 7
  • 23
  • 1
    This is only for consecutive subsequences right? what about non-consecutive? – Littlish Dec 19 '19 at 08:38
  • This answer seems incorrect. It seems to misunderstand the question. The question asks about subsequences (not necessarily consecutive; may have gaps in them). Your answer would work if we wanted a contiguous subsequences, but it doesn't work for the problem stated in the question. I encourage you to delete your answer to avoid confusing people and to avoid having this question be marked as "already answered". – D.W. Jan 02 '20 at 19:00