词条 | Longest alternating subsequence |
释义 |
In combinatorial mathematics, probability, and computer science, in the longest alternating subsequence problem, one wants to find a subsequence of a given sequence in which the elements are in alternating order, and in which the sequence is as long as possible. Formally, if is a sequence of distinct real numbers, then the subsequence is alternating name="Stanleybook">{{citation Similarly, is reverse alternating (or up-down) if Let denote the length (number of terms) of the longest alternating subsequence of . For example, if we consider some of the permutations of the integers 1,2,3,4,5, we have that
Efficient algorithmsThe longest alternating subsequence problem is solvable in time , where is the length of the original sequence.{{Citation needed|date=October 2016}} Distributional resultsIf is a random permutation of the integers and , then it is possible to show name="widom">{{citation | doi = 10.1307/mmj/1220879431 | last1 = Stanley | first1 = Richard P. | author1-link = Richard_P._Stanley | journal = Michigan Math. J. | pages = 675–687 | title = Longest alternating subsequences of permutations | volume = 57 | year = 2008| arxiv = math/0511419}}name="hr">{{citation | url = http://www.combinatorics.org/Volume_17/Abstracts/v17i1r168.html | last1 = Houdré | first1 = Christian | last2 = Restrepo | first2 = Ricardo | journal = Electron. J. Combin. | title = A probabilistic approach to the asymptotics of the length of the longest alternating subsequence | volume = 17 | pages = Research Paper 168, 19 | year = 2010}} that Moreover, as , the random variable , appropriately centered and scaled, converges to a standard normal distribution. Online algorithmsThe longest alternating subsequence problem has also been studied in the setting of online algorithms, in which the elements of are presented in an online fashion, and a decision maker needs to decide whether to include or exclude each element at the time it is first presented, without any knowledge of the elements that will be presented in the future, and without the possibility of recalling on preceding observations. Given a sequence of independent random variables with common continuous distribution , it is possible to construct a selection procedure that maximizes the expected number of alternating selections. Such expected values can be tightly estimated, and it equals .[1] As , the optimal number of online alternating selections appropriately centered and scaled converges to a normal distribution.[2] See also
References1. ^{{citation | doi = 10.1239/jap/1324046022 | last1 = Arlotto | first1 = Alessandro | last2 = Chen | first2 = Robert W. | last3 = Shepp | first3 = Lawrence A. | author3-link = Lawrence_Shepp | last4 = Steele | first4 = J. Michael | author4-link = J._Michael_Steele | journal = J. Appl. Probab. | pages = 1114–1132 | title = Online selection of alternating subsequences from a random sample | volume = 48 | issue = 4 | year = 2011| arxiv = 1105.1558}} 2. ^{{citation | doi = 10.1239/aap/1401369706 | last1 = Arlotto | first1 = Alessandro | last2 = Steele | first2 = J. Michael | author2-link = J._Michael_Steele | journal = Adv. Appl. Probab. | pages = 536–559 | title = Optimal online selection of an alternating subsequence: a central limit theorem | volume = 46 | issue = 2 | year = 2014}} 4 : Problems on strings|Permutations|Combinatorics|Dynamic programming |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。