Almost-Increasing Subsequence Problem
Exploring the concept of almost-increasing subsequences as the longest subsequences that can be converted to increasing subsequences by adding a value within a fixed limit to each element. The article presents an improved algorithm with O(n.logk) time complexity to solve the problem efficiently.
Uploaded on | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
The longest almost-increasing subsequence Amr Elmasry Information Processing Letters, Volume 110, Issue 16 (2010), 655 658 Presenter: Wan-Ni Ou Date: July 23, 2024 1
Abstract Given a sequence of n elements, we introduce the notion of an almost- increasing subsequence as the longest subsequence that can be converted to an increasing subsequence by possibly adding a value, that is at most a fixed constant, to each of the elements. We show how to optimally construct such subsequence in O(n logk) time, where k is the length of the output subsequence. 2
Longest almost-increasing subsequence 7, 15, 2, 14, 14, 6, 8, 11, 17, 15, 14, 13 c = 2 LaIS = 7, 15, 14, 14, 15, 14 3
The basic algorithm 7, 15, 2, 14, 14, 6, 8, 11, 17, 15, 14,13 C = 2 Length: LaIS Indexes: Task 1: index i lengt Task 2: c 4
The improved algorithm 7, 15, 2, 14, 14, 6, 8, 11, 17, 15, 14,13 C = 2 Step1 find an element which is greater than xi, insert xi. Step2 delete the successor which is greater than xi + c. 5
pseudo-code Uses 6
Conclusion Proposed an improved algorithm to solve the LaIS problem. Time Complexity: O(n logk) 7
Thanks 8
