Algorithms for K disjoint maximum subarrays (2006)
AuthorsSung, S.B., Takaoka, T.show all
The 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.
CitationBae, 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.
This citation is automatically generated and may be unreliable. Use as a guide only.