{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,17]],"date-time":"2026-01-17T19:28:56Z","timestamp":1768678136722,"version":"3.49.0"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,2,17]],"date-time":"2022-02-17T00:00:00Z","timestamp":1645056000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,2,17]],"date-time":"2022-02-17T00:00:00Z","timestamp":1645056000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003385","name":"Georg-August-Universit\u00e4t G\u00f6ttingen","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003385","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,4]]},"abstract":"Abstract<\/jats:title>For$$k\\ge 3$$<\/jats:tex-math>k<\/mml:mi>\u2265<\/mml:mo>3<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, ak-rollercoaster<\/jats:italic>is a sequence of numbers whose every maximal contiguous subsequence, that is increasing or decreasing, has length at leastk<\/jats:italic>; 3-rollercoasters are called simply rollercoasters. Given a sequence of distinct real numbers, we are interested in computing its maximum-length (not necessarily contiguous) subsequence that is ak<\/jats:italic>-rollercoaster. Biedl et al. (in: ICALP, volume 107 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp 18:1\u201318:15, 2018) have shown that each sequence ofn<\/jats:italic>distinct real numbers contains a rollercoaster of length at least$$\\lceil n\/2\\rceil $$<\/jats:tex-math>\u2308<\/mml:mo>n<\/mml:mi>\/<\/mml:mo>2<\/mml:mn>\u2309<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>for$$n>7$$<\/jats:tex-math>n<\/mml:mi>><\/mml:mo>7<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and that a longest rollercoaster contained in such a sequence can be computed in$$O(n\\log n)$$<\/jats:tex-math>O<\/mml:mi>(<\/mml:mo>n<\/mml:mi>log<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-time (or faster, in$$O(n \\log \\log n)$$<\/jats:tex-math>O<\/mml:mi>(<\/mml:mo>n<\/mml:mi>log<\/mml:mo>log<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>time, when the input sequence is a permutation of$$\\{1,\\ldots ,n\\}$$<\/jats:tex-math>{<\/mml:mo>1<\/mml:mn>,<\/mml:mo>\u2026<\/mml:mo>,<\/mml:mo>n<\/mml:mi>}<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>). They have also shown that every sequence of$$n\\geqslant (k-1)^2+1$$<\/jats:tex-math>n<\/mml:mi>\u2a7e<\/mml:mo>(<\/mml:mo>k<\/mml:mi>-<\/mml:mo>1<\/mml:mn>)<\/mml:mo><\/mml:mrow>2<\/mml:mn><\/mml:msup>+<\/mml:mo>1<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>distinct real numbers contains ak<\/jats:italic>-rollercoaster of length at least$$\\frac{n}{2(k-1)}-\\frac{3k}{2}$$<\/jats:tex-math>n<\/mml:mi>2<\/mml:mn>(<\/mml:mo>k<\/mml:mi>-<\/mml:mo>1<\/mml:mn>)<\/mml:mo><\/mml:mrow><\/mml:mfrac>-<\/mml:mo>3<\/mml:mn>k<\/mml:mi><\/mml:mrow>2<\/mml:mn><\/mml:mfrac><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and gave an$$O(nk\\log n)$$<\/jats:tex-math>O<\/mml:mi>(<\/mml:mo>n<\/mml:mi>k<\/mml:mi>log<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-time (respectively,$$O(n k\\log \\log n)$$<\/jats:tex-math>O<\/mml:mi>(<\/mml:mo>n<\/mml:mi>k<\/mml:mi>log<\/mml:mo>log<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-time) algorithm computing a longestk<\/jats:italic>-rollercoaster in a sequence of lengthn<\/jats:italic>(respectively, a permutation of$$\\{1,\\ldots ,n\\}$$<\/jats:tex-math>{<\/mml:mo>1<\/mml:mn>,<\/mml:mo>\u2026<\/mml:mo>,<\/mml:mo>n<\/mml:mi>}<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>). In this paper, we give an$$O(nk^2)$$<\/jats:tex-math>O<\/mml:mi>(<\/mml:mo>n<\/mml:mi>k<\/mml:mi>2<\/mml:mn><\/mml:msup>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-time algorithm computing the length of a longestk<\/jats:italic>-rollercoaster contained in a sequence ofn<\/jats:italic>distinct real numbers; hence, for constantk<\/jats:italic>, our algorithm computes the length of a longestk<\/jats:italic>-rollercoaster in optimal linear time. The algorithm can be easily adapted to output the respectivek<\/jats:italic>-rollercoaster. In particular, this improves the results of Biedl et al. (2018), by showing that a longest rollercoaster can be computed in optimal linear time. We also present an algorithm computing the length of a longestk<\/jats:italic>-rollercoaster in$$O(n \\log ^2 n)$$<\/jats:tex-math>O<\/mml:mi>(<\/mml:mo>n<\/mml:mi>log<\/mml:mo>2<\/mml:mn><\/mml:msup>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-time, that is, subquadratic even for large values of$$k\\le n$$<\/jats:tex-math>k<\/mml:mi>\u2264<\/mml:mo>n<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Again, the rollercoaster can be easily retrieved. Finally, we show an$$\\Omega (n \\log k)$$<\/jats:tex-math>\u03a9<\/mml:mi>(<\/mml:mo>n<\/mml:mi>log<\/mml:mo>k<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>lower bound for the number of comparisons in any comparison-based algorithm computing the length of a longestk<\/jats:italic>-rollercoaster.<\/jats:p>","DOI":"10.1007\/s00453-021-00908-6","type":"journal-article","created":{"date-parts":[[2022,2,17]],"date-time":"2022-02-17T05:02:33Z","timestamp":1645074153000},"page":"1081-1106","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Fast and Longest Rollercoasters"],"prefix":"10.1007","volume":"84","author":[{"given":"Pawe\u0142","family":"Gawrychowski","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6094-3324","authenticated-orcid":false,"given":"Florin","family":"Manea","sequence":"additional","affiliation":[]},{"given":"Rados\u0142aw","family":"Serafin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,2,17]]},"reference":[{"issue":"1\u20132","key":"908_CR1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0166-218X(90)90124-U","volume":"27","author":"A Aggarwal","year":"1990","unstructured":"Aggarwal, A., Klawe, M.M.: Applications of generalized matrix searching to geometric algorithms. Discrete Appl. Math. 27(1\u20132), 3\u201323 (1990)","journal-title":"Discrete Appl. Math."},{"key":"908_CR2","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/BF01840359","volume":"2","author":"A Aggarwal","year":"1987","unstructured":"Aggarwal, A., Klawe, M.M., Moran, S., Shor, P.W., Wilber, R.E.: Geometric applications of a matrix-searching algorithm. Algorithmica 2, 195\u2013208 (1987)","journal-title":"Algorithmica"},{"key":"908_CR3","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1090\/S0273-0979-99-00796-X","volume":"36","author":"D Aldous","year":"1999","unstructured":"Aldous, D., Diaconis, P.: Longest increasing subsequences: from patience sorting to the Baik\u2013Deift\u2013Johansson theorem. Bull. Am. Math. Soc. 36, 413\u2013432 (1999)","journal-title":"Bull. Am. Math. Soc."},{"issue":"1","key":"908_CR4","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1016\/S0020-0190(00)00124-1","volume":"76","author":"S Bespamyatnikh","year":"2000","unstructured":"Bespamyatnikh, S., Segal, M.: Enumerating longest increasing subsequences and patience sorting. Inf. Process. Lett. 76(1), 7\u201311 (2000)","journal-title":"Inf. Process. Lett."},{"key":"908_CR5","unstructured":"Biedl, T.C., Biniaz, A., Cummings, R., Lubiw, A., Manea, F., Nowotka, D., Shallit, J.: Rollercoasters and caterpillars. In: ICALP, volume 107 of LIPIcs, pp. 18:1\u201318:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018)"},{"issue":"2","key":"908_CR6","doi-asserted-by":"publisher","first-page":"845","DOI":"10.1137\/18M1192226","volume":"33","author":"TC Biedl","year":"2019","unstructured":"Biedl, T.C., Biniaz, A., Cummings, R., Lubiw, A., Manea, F., Nowotka, D., Shallit, J.: Rollercoasters: Long sequences without short runs. SIAM J. Discrete Math. 33(2), 845\u2013861 (2019). (This extends the conference paper [5])","journal-title":"SIAM J. Discrete Math."},{"key":"908_CR7","doi-asserted-by":"crossref","unstructured":"Biedl, T.C., Chan, T.M., Derka, M., Jain, K., Lubiw, A.: Improved bounds for drawing trees on fixed points with L-shaped edges. In: Graph Drawing and Network Visualization\u201425th International Symposium, GD 2017, Revised Selected Papers, volume 10692 of Lecture Notes in Computer Science, pp. 305\u2013317. Springer (2017)","DOI":"10.1007\/978-3-319-73915-1_24"},{"issue":"3","key":"908_CR8","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1137\/0217026","volume":"17","author":"B Chazelle","year":"1988","unstructured":"Chazelle, B.: A functional approach to data structures and its use in multidimensional searching. SIAM J. Comput. 17(3), 427\u2013462 (1988)","journal-title":"SIAM J. Comput."},{"issue":"9","key":"908_CR9","doi-asserted-by":"publisher","first-page":"1054","DOI":"10.1016\/j.ic.2010.04.003","volume":"208","author":"M Crochemore","year":"2010","unstructured":"Crochemore, M., Porat, E.: Fast computation of a longest increasing subsequence and application. Inf. Comput. 208(9), 1054\u20131059 (2010)","journal-title":"Inf. Comput."},{"issue":"1","key":"908_CR10","doi-asserted-by":"publisher","first-page":"161","DOI":"10.2307\/1969503","volume":"51","author":"RP Dilworth","year":"1950","unstructured":"Dilworth, R.P.: A decomposition theorem for partially ordered sets. Ann. Math. 51(1), 161\u2013166 (1950)","journal-title":"Ann. Math."},{"key":"908_CR11","first-page":"463","volume":"2","author":"P Erd\u0151s","year":"1935","unstructured":"Erd\u0151s, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math. 2, 463\u2013470 (1935)","journal-title":"Compos. Math."},{"issue":"1","key":"908_CR12","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0012-365X(75)90103-X","volume":"11","author":"ML Fredman","year":"1975","unstructured":"Fredman, M.L.: On computing the length of longest increasing subsequences. Discrete Math. 11(1), 29\u201335 (1975)","journal-title":"Discrete Math."},{"issue":"4","key":"908_CR13","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0020-0190(86)90028-1","volume":"22","author":"H Gajewska","year":"1986","unstructured":"Gajewska, H., Tarjan, R.E.: Deques with heap order. Inf. Process. Lett. 22(4), 197\u2013200 (1986)","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"908_CR14","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1145\/359581.359603","volume":"20","author":"JW Hunt","year":"1977","unstructured":"Hunt, J.W., Szymanski, T.G.: A fast algorithm for computing longest common subsequences. Commun. ACM 20(5), 350\u2013353 (1977)","journal-title":"Commun. ACM"},{"key":"908_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17333-2","volume-title":"Patterns in Permutations and Words","author":"S Kitaev","year":"2011","unstructured":"Kitaev, S.: Patterns in Permutations and Words. Springer, Berlin (2011)"},{"key":"908_CR16","doi-asserted-by":"crossref","unstructured":"Linton, S., Ru\u0161kuc, N., Vatter, V. (eds.): Permutation Patterns. London Mathematical Society Lecture Note Series, vol. 376. Cambridge (2010)","DOI":"10.1017\/CBO9780511902499"},{"key":"908_CR17","doi-asserted-by":"crossref","unstructured":"Romik, D.: The Surprising Mathematics of Longest Increasing Subsequences. Cambridge (2015)","DOI":"10.1017\/CBO9781139872003"},{"key":"908_CR18","doi-asserted-by":"publisher","first-page":"179","DOI":"10.4153\/CJM-1961-015-3","volume":"13","author":"C Schensted","year":"1961","unstructured":"Schensted, C.: Longest increasing and decreasing subsequences. Can. J. Math. 13, 179\u2013191 (1961)","journal-title":"Can. J. Math."},{"key":"908_CR19","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/978-1-4612-0801-3_9","volume-title":"Discrete Probability and Algorithms","author":"JM Steele","year":"1995","unstructured":"Steele, J.M.: Variations on the monotone subsequence theme of Erd\u0151s and Szekeres. In: Aldous, D., Diaconis, P., Spencer, J., Steele, J.M. (eds.) Discrete Probability and Algorithms, pp. 111\u2013131. Springer, New York (1995)"},{"key":"908_CR20","unstructured":"Sun, X., Woodruff, D.P.: The communication and streaming complexity of computing the longest common and increasing subsequences. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201907, pp. 336\u2013345. Society for Industrial and Applied Mathematics (2007)"},{"issue":"4","key":"908_CR21","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1007\/s00453-013-9830-z","volume":"71","author":"A Tiskin","year":"2015","unstructured":"Tiskin, A.: Fast distance multiplication of unit-Monge matrices. Algorithmica 71(4), 859\u2013888 (2015)","journal-title":"Algorithmica"},{"key":"908_CR22","unstructured":"Weimann, O.: Accelerating Dynamic Programming. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, USA (2009)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00908-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00908-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00908-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T05:35:17Z","timestamp":1674797717000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00908-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,17]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["908"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00908-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,17]]},"assertion":[{"value":"9 August 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 November 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 February 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}