{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T18:42:09Z","timestamp":1760208129551,"version":"build-2065373602"},"reference-count":14,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2017,1,4]],"date-time":"2017-01-04T00:00:00Z","timestamp":1483488000000},"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>We present efficient sequential and parallel algorithms for the maximum sum (MS) problem, which is to maximize the sum of some shape in the data array. We deal with two MS problems; the maximum subarray (MSA) problem and the maximum convex sum (MCS) problem. In the MSA problem, we find a rectangular part within the given data array that maximizes the sum in it. The MCS problem is to find a convex shape rather than a rectangular shape that maximizes the sum. Thus, MCS is a generalization of MSA. For the MSA problem,     O ( n )     time parallel algorithms are already known on an     ( n , n )     2D array of processors. We improve the communication steps from     2 n \u2212 1     to n, which is optimal. For the MCS problem, we achieve the asymptotic time bound of     O ( n )     on an     ( n , n )     2D array of processors. We provide rigorous proofs for the correctness of our parallel algorithm based on Hoare logic and also provide some experimental results of our algorithm that are gathered from the Blue Gene\/P super computer. Furthermore, we briefly describe how to compute the actual shape of the maximum convex sum.<\/jats:p>","DOI":"10.3390\/a10010005","type":"journal-article","created":{"date-parts":[[2017,1,4]],"date-time":"2017-01-04T09:39:32Z","timestamp":1483522772000},"page":"5","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Algorithms for the Maximum Sum Problems"],"prefix":"10.3390","volume":"10","author":[{"given":"Sung","family":"Bae","sequence":"first","affiliation":[{"name":"Algorithm Research Institute, Christchurch 8053, New Zealand"}]},{"given":"Tong-Wook","family":"Shinn","sequence":"additional","affiliation":[{"name":"Algorithm Research Institute, Christchurch 8053, New Zealand"}]},{"given":"Tadao","family":"Takaoka","sequence":"additional","affiliation":[{"name":"Algorithm Research Institute, Christchurch 8053, New Zealand"},{"name":"Computer Science and Software Engineering, University of Canterbury, Christchurch 8140, New Zealand"}]}],"member":"1968","published-online":{"date-parts":[[2017,1,4]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1297","DOI":"10.1126\/science.1170411","article-title":"Tony hey and alex szalay: Beyond the data deluge","volume":"323","author":"Bell","year":"2009","journal-title":"Science"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1038\/scientificamerican0515-58","article-title":"The search for a new machine","volume":"312","author":"Pavlus","year":"2015","journal-title":"Sci. Am."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1145\/383891.383893","article-title":"Data mining with optimized two-dimensional association rules","volume":"26","author":"Fukuda","year":"2001","journal-title":"ACM Trans. Database Syst."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1145\/1968.381154","article-title":"Perspective on performance","volume":"27","author":"Bentley","year":"1984","journal-title":"Commun. ACM"},{"key":"ref_5","unstructured":"Tamaki, H., and Tokuyama, T. (1998, January 25\u201327). Algorithms for the maximum subarray problem based on matrix multiplication. Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1998), San Francisco, CA, USA."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/S1571-0661(04)00313-5","article-title":"Efficient algorithms for the maximum subarray problem by distance matrix multiplication","volume":"61","author":"Takaoka","year":"2002","journal-title":"Electr. Notes Theor. Comput. Sci."},{"key":"ref_7","unstructured":"Bae, S.E. (2007). Sequential and Parallel Algorithms for Generalized Maximum Subarray Problem. [Ph. D Thesis, University of Canterbury]."},{"key":"ref_8","unstructured":"Bae, S.E., and Takaoka, T. (2004, January 10\u201312). Algorithms for the Problem of K Maximum Sums and a VLSI Algorithm for the K Maximum Subarrays Problem. Proceedings of the 7th International Symposium on Parallel Architectures, Algorithms and Networks (I-SPAN 2004), Hong Kong, China."},{"key":"ref_9","unstructured":"Takaoka, T. (2014, January 20\u201323). Efficient parallel algorithms for the maximum subarray problem. Proceedings of the 12th Australasian Symposium on Parallel and Distributed Computing (AusPDC 2014), Auckland, New Zealand."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Alves, C.E.R., Caceres, E.N., and Song, S.W. (2004, January 19\u201322). BSP\/CGM Algorithms for Maximum Subsequence and Maximum Subarray. Proceedings of the 11th European PVM\/MPI Users\u2019 Group Meeting, Budapest, Hungary.","DOI":"10.1007\/978-3-540-30218-6_24"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"576","DOI":"10.1145\/363235.363259","article-title":"An axiomatic basis for computer programming","volume":"12","author":"Hoare","year":"1969","journal-title":"Commun. ACM"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1145\/360051.360224","article-title":"Verifying properties of parallel programs: An axiomatic approach","volume":"19","author":"Owicki","year":"1976","journal-title":"Commun. ACM"},{"key":"ref_13","unstructured":"Thaher, M. (2014). Efficient Algorithms for the Maximum Convex Sum Problem. [PhD Thesis, University of Canterbury]."},{"key":"ref_14","unstructured":"IBM: Parallel Environment Runtime Edition for Linux: MPI Programming Guide (SC23-7285-01) (7\/2015). Available online: http:\/\/publib.boulder.ibm.com\/epubs\/pdf\/c2372851.pdf."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/10\/1\/5\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T18:25:27Z","timestamp":1760207127000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/10\/1\/5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1,4]]},"references-count":14,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2017,3]]}},"alternative-id":["a10010005"],"URL":"https:\/\/doi.org\/10.3390\/a10010005","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2017,1,4]]}}}