Sung, S.B.Takaoka, T.2007-06-262007-06-262006Bae, S.E., Takaoka, T. (2006) Algorithms for K Disjoint Maximum Subarrays. Reading, UK: International Conference on Computational Science (ICCS 2006): Advancing Science through Computation, 28-31 May 2006. Lecture Notes in Computer Science (LNCS), 3994, Computational Science - ICCS 2006, 595-602.http://hdl.handle.net/10092/112The maximum subarray problem is to find the array portion that maximizes the sum of array elements in it. For K disjoint maximum subarrays, Ruzzo and Tompa gave an O(n) time solution for one-dimension. This solution is, however, difficult to extend to twodimensions. While a trivial solution of O(Kn³) time is easily obtainable for two-dimensions, little study has been undertaken to better this. We first propose an O(n + K log K) time solution for one-dimension. This is equivalent to Ruzzo and Tompa’s when order is considered. Based on this, we achieve O n³+Kn² log n) time for two-dimensions. This is cubic time when K ≤ n / log n.enConference Contributions - PublishedFields of Research::280000 Information, Computing and Communication Sciences::280300 Computer Software