Advertisement
Published in:
2006 | OriginalPaper | Chapter
Algorithm for K Disjoint Maximum Subarrays
Authors : Sung Eun Bae, Tadao Takaoka
Published in: Computational Science – ICCS 2006
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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 two-dimensions. While a trivial solution of
O
(
Kn
3
) 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
3
+
Kn
2
log
n
) time for two-dimensions. This is cubic time when
K
≤
n
/log
n
.