{"entities":{"Q2508973":{"pageid":2519716,"ns":120,"title":"Item:Q2508973","lastrevid":49949602,"modified":"2026-01-12T06:10:13Z","type":"item","id":"Q2508973","labels":{"en":{"language":"en","value":"Improved algorithms for the \\(k\\) maximum-sums problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5066112"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2508973$4AEBF2BD-B88B-46C0-8FF0-DCCAB06D4058","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c263bdbb82ac407e53467d95afa64797d534ad29","datavalue":{"value":{"text":"Improved algorithms for the \\(k\\) maximum-sums problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2508973$13F8C84C-E081-4B49-ABA5-FDEA18B1F979","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"88a70e21e5c9f17a292ec37e7be4b7eed40305d7","datavalue":{"value":"1155.68604","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2508973$F6234F9F-7B45-4907-BBD6-ADF21BFAF32E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"254508208651d138f996b88316078986a7f5e801","datavalue":{"value":{"entity-type":"item","numeric-id":976063,"id":"Q976063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2508973$23D8EE86-8A08-4036-9BE7-70398D1230DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"365219537a19f671a9a8ce5495e5f5c75f97e0c5","datavalue":{"value":{"entity-type":"item","numeric-id":348417,"id":"Q348417"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2508973$69FBFEC1-FC84-47DD-BBC7-E583CEEC15CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4b4fc3e63d2b43e95771ceb30f811868fa7e1fbf","datavalue":{"value":{"entity-type":"item","numeric-id":2508972,"id":"Q2508972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2508973$7B1C83D2-D710-48EF-B0AA-76FAA693FA84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ae4baaea64980ca8fbc3cb88c5fb2d37229ccd50","datavalue":{"value":{"entity-type":"item","numeric-id":294614,"id":"Q294614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2508973$78374D24-D140-47FC-806B-371294F57F5A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2508973$53747A24-F337-4C00-BD31-737F253EF1B8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"04d8047ef91e7ccd7af1b39494c1aad77dacfac1","datavalue":{"value":{"time":"+2006-10-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2508973$080AF011-D7B1-4E69-98CE-4FD628AD526F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e2532e1ba52600a83099eb08af85fe1ad2fe7d86","datavalue":{"value":"Given a sequence of n real numbers and an integer \\(k\\), \\(1\\leq k\\leq n(n-1)/2\\), the \\(k\\) maximum-sum segments problem is to locate the \\(k\\) segments whose sums are the \\(k\\) largest among all possible segment sums. Recently, \\textit{F. Bengtsson} and \\textit{J. Chen} [Lect. Notes Comput. Sci. 3341, 137--148 (2004; Zbl 1100.68643), Algorithmica 46, No. 1, 27--41 (2006; Zbl 1100.68124)] gave an \\(O(\\min{k+nlog^2n,n\\sqrt{k}})\\)-time algorithm for this problem. S. E. Bae and T. Takaoka later proposed a more efficient algorithm for small \\(k\\). In this paper, we propose an \\(O(n+k\\log(\\min\\{n,k\\}))\\)-time algorithm for the same problem, which is superior to both of them when \\(k\\) is \\(o(n \\log n)\\). We also give the first optimal algorithm for delivering the \\(k\\) maximum-sum segments in non-decreasing order if \\(k\\leq n\\). Then we develop an \\(O(n^{2d-1}+k\\log(\\min\\{n,k\\}))\\)-time algorithm for the \\(d\\)-dimensional version of the problem, where \\(d>1\\) and each dimension, without loss of generality, is of the same size \\(n\\). This improves the best previously known \\(O(n^{2d-1}C)\\)-time algorithm, also by Bengtsson and Chen, where \\(C=\\min \\{k+n\\log^2n, n\\sqrt{k}\\}\\). It should be pointed out that, given a two-dimensional array of size \\(m\\times n\\), our algorithm for finding the \\(k\\) maximum-sum subarrays is the first one achieving cubic time provided that \\(k\\) is \\(O(m^2n/\\log n)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2508973$862F9BC3-B71F-400C-B97B-C8CA547B63CE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2508973$E2762B1F-5D70-4AAF-9D43-659A9F3971BB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8325df272b6df93803a2266266f03b4e08252034","datavalue":{"value":"5066112","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2508973$5923E664-678B-48ED-8FD9-1F18E9981EEA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fdf5ad2ae840dccb19bc1863ceaf1595e1420353","datavalue":{"value":"maximum-sum subsequence","type":"string"},"datatype":"string"},"type":"statement","id":"Q2508973$66CA3D3E-B2BF-4698-AB2F-228B7B453ACC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"41c46c779a8626907ea8b1c1e42817c906e5f58e","datavalue":{"value":"maximum-sum subarray","type":"string"},"datatype":"string"},"type":"statement","id":"Q2508973$47D4C318-2964-43F0-9220-D223A4F85D45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4565fb70f87fb85f03800c1a0e35bd95a6b70db1","datavalue":{"value":"sequence analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q2508973$57857EB3-A81B-4A57-800E-D6CF9871B6F6","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"804e8a5cce0fcd46b73a89f7bf7f2e89fc4afb2d","datavalue":{"value":{"entity-type":"item","numeric-id":51445,"id":"Q51445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2508973$803A8FE1-1053-4E48-A90D-D5DBE4DCB189","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"5d91db24b453972fd3b31e9c72b9b0bb54493676","datavalue":{"value":{"entity-type":"item","numeric-id":22870,"id":"Q22870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2508973$886D64FE-2CAF-4934-8A0E-E93079485525","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2508973$466156DF-2837-4EF6-A895-443954B868C2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f7ebb17578234ead46438b4e5eb48f9c2c50b9f4","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2006.06.007","type":"string"},"datatype":"url"},"type":"statement","id":"Q2508973$3EC20D36-0D82-4A0A-BA46-D58716C9A942","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fc6b0ff63ce41c5ee8a59b44028d866444861df1","datavalue":{"value":"W2076768231","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2508973$DD79BCF5-38FD-4743-8892-42506C4111E3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a00e6fc3e37e91166507165b8276a390e1aa0f8c","datavalue":{"value":{"entity-type":"item","numeric-id":5716983,"id":"Q5716983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2508973$7C506DD6-1EB9-4A3C-B166-6056F098FF65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb119746cc0c954438117552bc55c66f1e678929","datavalue":{"value":{"entity-type":"item","numeric-id":5712105,"id":"Q5712105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2508973$4F278B19-EEA9-40C2-89D3-8D28232CD9BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e47000fb8eb2d57f51772c251b10d72127cdc3bd","datavalue":{"value":{"entity-type":"item","numeric-id":5712120,"id":"Q5712120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2508973$8719B762-8EB9-43E3-9694-F43A93373C3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b10582db5100998373b5197423d90ec1fe44cef8","datavalue":{"value":{"entity-type":"item","numeric-id":1044737,"id":"Q1044737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2508973$F0272075-0023-4401-A623-A74899956EE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8d1ca8b17d76ed1e3c210d34ceb6b7dc0b7fddd","datavalue":{"value":{"entity-type":"item","numeric-id":3559780,"id":"Q3559780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2508973$CE3414A3-A086-4B0B-99D3-82AB83EDED0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"606ce2e3b04864c04cb0d60b6cd5729547188b45","datavalue":{"value":{"entity-type":"item","numeric-id":1137400,"id":"Q1137400"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2508973$44277BEE-C2B1-4B13-85DE-C9F1F70803CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de9806f436c79f0d9971f0dea14138562f141617","datavalue":{"value":{"entity-type":"item","numeric-id":5897884,"id":"Q5897884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2508973$1DCF03AB-0EAC-4A7F-8A93-B6DC7F89527C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"10e1a1328245eab21984047639207bd038fd176e","datavalue":{"value":{"entity-type":"item","numeric-id":1872726,"id":"Q1872726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2508973$163D4181-BFCD-42F2-8B8D-5A9D4FB73D3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"899030754e56750b28c82d14ff3657c98d438691","datavalue":{"value":{"entity-type":"item","numeric-id":4250212,"id":"Q4250212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2508973$481457A0-59FA-4CF2-B4B3-72D6633B0CB8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"315931e0fce79d2bdb8d36134fa6ba70fb743689","datavalue":{"value":"10.1016/J.TCS.2006.06.007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2508973$32AED1B5-E904-477E-B211-BDA6A04FEF8D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c0d9059a8159755e7b322518d445a46f9aab4e1","datavalue":{"value":{"entity-type":"item","numeric-id":5897912,"id":"Q5897912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f57a96b96f2b10d833e756201e7f2549daccf5ef","datavalue":{"value":{"amount":"+0.9957910776138306","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2508973$3E2330F0-8CE7-4EB6-B0D4-F4EBDB281167","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1cd8ef1d457d09491912547c3a87bf5cbc65a3f7","datavalue":{"value":{"entity-type":"item","numeric-id":5712105,"id":"Q5712105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b84aa7a6512a691575eef75f0d5a1fa0c97ffeb","datavalue":{"value":{"amount":"+0.923984944820404","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2508973$7E5DCD99-23A1-447F-BD43-731F3EA25FB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"be2a983765fab2262448b38ceb94279243d53db8","datavalue":{"value":{"entity-type":"item","numeric-id":2509030,"id":"Q2509030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"381dcc6b8a97298abc80109010098124ec0fca75","datavalue":{"value":{"amount":"+0.9185419678688048","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2508973$4F149290-E8AE-4E19-9FCE-8505AFF67852","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ec24d9282cb7458bd72af7901b28d371723043c7","datavalue":{"value":{"entity-type":"item","numeric-id":5716983,"id":"Q5716983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15ee0283be49e0adf6cad3a898adf87c65b116c1","datavalue":{"value":{"amount":"+0.9067885875701904","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2508973$596D2BD3-9BCF-4F14-826D-B736B9D0C89A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f1ae51210b3dd5faa136a3024f912d1ccd13e48","datavalue":{"value":{"entity-type":"item","numeric-id":3525591,"id":"Q3525591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"19760268ce3a29e3b2237bd2f275c1154b91c278","datavalue":{"value":{"amount":"+0.9031180739402772","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2508973$6297FEF1-AEF5-46FC-8059-BEB61DED0106","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2508973","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2508973"}}}}}