{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T21:45:22Z","timestamp":1760132722008,"version":"build-2065373602"},"reference-count":17,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2023,11,14]],"date-time":"2023-11-14T00:00:00Z","timestamp":1699920000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The maximum sum subarray problem is to find a contiguous subarray with the largest sum. The history of algorithms to address this problem is recounted, culminating in what is known as Kadane\u2019s algorithm. However, that algorithm is not the algorithm Kadane intended. Nonetheless, the algorithm known as Kadane\u2019s has found many uses, some of which are recounted here. The algorithm Kadane intended is reported here, and compared to the algorithm attributed to Kadane. They are both linear in time, employ just a few words of memory, and use a dynamic programming structure. The results proved here show that these two algorithms differ only in the case of an input consisting of only negative numbers. In that case, the algorithm Kadane intended is more informative than the algorithm attributed to him.<\/jats:p>","DOI":"10.3390\/a16110519","type":"journal-article","created":{"date-parts":[[2023,11,14]],"date-time":"2023-11-14T02:20:37Z","timestamp":1699928437000},"page":"519","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Two Kadane Algorithms for the Maximum Sum Subarray Problem"],"prefix":"10.3390","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1548-5912","authenticated-orcid":false,"given":"Joseph B.","family":"Kadane","sequence":"first","affiliation":[{"name":"Department of Statistics and Data Science, Dietrich College of Humanities and Social Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, USA"}]}],"member":"1968","published-online":{"date-parts":[[2023,11,14]]},"reference":[{"key":"ref_1","unstructured":"von Neumann, J., and Morgenstern, O. (1944). Theory of Games and Economic Behavior, Princeton University Press."},{"key":"ref_2","unstructured":"Savage, L. (1954). Foundations of Statistics, J. Wiley and Sons."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Dantzig, G. (1963). Linear Programming and Extensions, Princeton University Press.","DOI":"10.7249\/R366"},{"key":"ref_4","unstructured":"Oved, S. (1972). Inequalities III, Proceedings of the Third Symposium on Inequalities, Los Angeles, CA, USA, 1\u20139 September 1969, Academic Press. Dedicated to the Memory of Theodore S. Motzkin."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1145\/358234.381162","article-title":"Algorithm Design Techniques","volume":"27","author":"Bentley","year":"1984","journal-title":"Commun. ACM"},{"key":"ref_6","unstructured":"(2023, November 02). Maximum Sum Rectangle in a 2D Matrix. Available online: https:\/\/www.geeksforgeeks.org\/maximum-sum-rectangle-in-a-2d-matrix-dp-27."},{"key":"ref_7","unstructured":"(2023, November 02). Maximum Sum Rectangle in a 2D Matrix\u2014Kadane\u2019s Algorithm Application (Dynamic Programming). Available online: https:\/\/www.youtube.com\/watch?V=FgseNO-6Gk."},{"key":"ref_8","unstructured":"Ray, T. (2023, November 02). Maximum Sum Rectangular Submatrix in Matrix Dynamic Programming\/2D Kadane. Available online: https:\/\/www.youtube.com\/watch?v=yCQN096CwWM."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Saleh, S., Abdellah, M., Abdel Raouf, A., and Kadah, Y. (2012, January 20\u201321). High Performance CUDA-based Implementation for the 2D Version of the Maximum Subarray Problem (MSP). Proceedings of the 2012 Cairo International Biomedical Engineering Conference, Giza, Egypt.","DOI":"10.1109\/CIBEC.2012.6473291"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Waddell, S., Takaoka, T., Read, T., and Candy, R. (2012, January 12\u201316). Maximum subarray algorithms for use in optical and radio astronomy. Proceedings of the SPIE 8500 Image Reconstruction from Incomplete Data VII, San Diego, CA, USA.","DOI":"10.1117\/12.928318"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1038\/s41588-018-0316-4","article-title":"Fast and accurate genomic analyses using genome graphs","volume":"51","author":"Rakocevic","year":"2019","journal-title":"Nat. Genet."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"34838","DOI":"10.1038\/srep34838","article-title":"IncScore: Alignment-free identification of long noncoding RNA from assembled novel transcripts","volume":"6","author":"Zhao","year":"2016","journal-title":"Sci. Rep."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Wu, J., Lee, W.P., Ward, A., Walker, J.A., Konkel, M.K., Batzer, M.A., and Gabor, T. (2014). Tangram: A comprehensive toolbox for mobile element insertion detection. BMC Genom., 15.","DOI":"10.1186\/1471-2164-15-795"},{"key":"ref_14","unstructured":"Xiang, J., Dong, Y., Xue, X., and Xiang, H. (2019). Transactions on Biomedical Circuits and Systems, IEEE."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1007\/s40745-017-0117-0","article-title":"Using Maximum Sum Subarrays for Approximate String Matching","volume":"4","author":"Aygun","year":"2017","journal-title":"Ann. Data Sci."},{"key":"ref_16","unstructured":"(2023, November 02). Available online: https:\/\/leetcode.com\/problems\/maximum-subarray\/."},{"key":"ref_17","unstructured":"Miriello, B. (2023, November 02). Kadane\u2019s Algorithm: Gateway to Dynamic Programming. Available online: https:\/\/levelup.gitconnected.com\/kadanes-algorithm-gateway-to-dynamic-programming-26e95ec13c7f."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/11\/519\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T21:22:33Z","timestamp":1760131353000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/11\/519"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,14]]},"references-count":17,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2023,11]]}},"alternative-id":["a16110519"],"URL":"https:\/\/doi.org\/10.3390\/a16110519","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2023,11,14]]}}}