Algorithms for K disjoint maximum subarrays
| dc.contributor.author | Sung, S.B. | |
| dc.contributor.author | Takaoka, T. | |
| dc.date.accessioned | 2007-06-26T03:17:14Z | |
| dc.date.available | 2007-06-26T03:17:14Z | |
| dc.date.issued | 2006 | en |
| dc.description.abstract | 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. | en |
| dc.identifier.citation | Bae, 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. | en |
| dc.identifier.uri | http://hdl.handle.net/10092/112 | |
| dc.language.iso | en | |
| dc.publisher | University of Canterbury. Computer Science and Software Engineering. | en |
| dc.rights.uri | https://hdl.handle.net/10092/17651 | en |
| dc.subject.marsden | Fields of Research::280000 Information, Computing and Communication Sciences::280300 Computer Software | en |
| dc.title | Algorithms for K disjoint maximum subarrays | en |
| dc.type | Conference Contributions - Published |
Files
Original bundle
1 - 1 of 1