{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T23:17:57Z","timestamp":1771024677037,"version":"3.50.1"},"reference-count":29,"publisher":"World Scientific Pub Co Pte Ltd","issue":"02","funder":[{"DOI":"10.13039\/100020595","name":"National Science and Technology Council","doi-asserted-by":"publisher","award":["MOST 108-2221-E-110-031"],"award-info":[{"award-number":["MOST 108-2221-E-110-031"]}],"id":[{"id":"10.13039\/100020595","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2025,2]]},"abstract":"<jats:p> The longest increasing subsequence (LIS) problem aims to find the subsequence exhibiting an increasing trend in a numeric sequence with the maximum length. In this paper, we generalize the LIS problem to the longest wave subsequence (LWS) problem, which encompasses two versions: LWSt and LWSr. Given a numeric sequence [Formula: see text] of distinct values and a target trend sequence [Formula: see text], the LWSt problem aims to identify the longest subsequence of [Formula: see text] that preserves the trend of the prefix of [Formula: see text]. And, the LWSr problem aims to find the longest subsequence of [Formula: see text] within [Formula: see text] segments, alternating increasing and decreasing subsequences. We propose two efficient algorithms for solving the two versions of the LWS problem. For the LWSt problem, the time complexity of our algorithm is O[Formula: see text], where [Formula: see text] represents the length of the given numeric sequence [Formula: see text]. Additionally, we propose an O[Formula: see text]-time algorithm for solving the LWSr problem. In both algorithms, we utilize the priority queues for the insertion, deletion, and successor operations. <\/jats:p>","DOI":"10.1142\/s012905412450014x","type":"journal-article","created":{"date-parts":[[2024,7,16]],"date-time":"2024-07-16T07:48:43Z","timestamp":1721116123000},"page":"203-218","source":"Crossref","is-referenced-by-count":1,"title":["The Longest Wave Subsequence Problem: Generalizations of the Longest Increasing Subsequence Problem"],"prefix":"10.1142","volume":"36","author":[{"given":"Guan-Zhi","family":"Chen","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, National Sun Yat-sen University, Kaohsiung, Taiwan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6643-5523","authenticated-orcid":false,"given":"Chang-Biau","family":"Yang","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, National Sun Yat-sen University, Kaohsiung, Taiwan"}]},{"given":"Yu-Cheng","family":"Chang","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, National Sun Yat-sen University, Kaohsiung, Taiwan"}]}],"member":"219","published-online":{"date-parts":[[2024,7,12]]},"reference":[{"key":"S012905412450014XBIB001","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2013.03.013"},{"key":"S012905412450014XBIB002","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.03.057"},{"key":"S012905412450014XBIB003","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00124-1"},{"key":"S012905412450014XBIB004","doi-asserted-by":"publisher","DOI":"10.1007\/BF01683268"},{"key":"S012905412450014XBIB005","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2015.10.005"},{"key":"S012905412450014XBIB006","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2014.10.018"},{"key":"S012905412450014XBIB007","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/30.5.420"},{"key":"S012905412450014XBIB008","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2010.04.003"},{"key":"S012905412450014XBIB009","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/27.11.2369"},{"key":"S012905412450014XBIB010","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.05.022"},{"key":"S012905412450014XBIB011","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90103-X"},{"key":"S012905412450014XBIB012","doi-asserted-by":"publisher","DOI":"10.1145\/359146.359148"},{"key":"S012905412450014XBIB013","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2006.04.023"},{"key":"S012905412450014XBIB014","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.08.022"},{"key":"S012905412450014XBIB015","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkg548"},{"key":"S012905412450014XBIB016","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2014.11.013"},{"key":"S012905412450014XBIB017","doi-asserted-by":"publisher","DOI":"10.1145\/359581.359603"},{"key":"S012905412450014XBIB018","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.10.006"},{"key":"S012905412450014XBIB020","doi-asserted-by":"publisher","DOI":"10.1137\/0206024"},{"key":"S012905412450014XBIB021","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2013.03.015"},{"key":"S012905412450014XBIB023","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2020.02.024"},{"key":"S012905412450014XBIB024","volume-title":"Introduction to Algorithms: A Creative Approach","author":"Manber U.","year":"1989","edition":"1"},{"key":"S012905412450014XBIB025","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/9.2.183"},{"key":"S012905412450014XBIB026","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1961-015-3"},{"issue":"11","key":"S012905412450014XBIB027","first-page":"2596","volume":"21","author":"Stephens S. M.","year":"2005","journal-title":"Nucleic Acids Research"},{"key":"S012905412450014XBIB028","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2007.1006"},{"key":"S012905412450014XBIB029","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008001603737"},{"issue":"2","key":"S012905412450014XBIB030","first-page":"173","volume":"10","author":"Tseng C.-T.","year":"2009","journal-title":"Journal of Internet Technology"},{"key":"S012905412450014XBIB031","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.10.014"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S012905412450014X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,26]],"date-time":"2025-02-26T09:13:40Z","timestamp":1740561220000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S012905412450014X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,12]]},"references-count":29,"journal-issue":{"issue":"02","published-print":{"date-parts":[[2025,2]]}},"alternative-id":["10.1142\/S012905412450014X"],"URL":"https:\/\/doi.org\/10.1142\/s012905412450014x","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,7,12]]}}}