Improved Algorithms for the K-Mazimum Subarray Problem for Small K
The maximum subarray problem for a one-or twodimensional array is to find the array portion that maiximizes the sum of array elements in it. The Kmaximum subarray problem is to find the K subarrays with largest sums. We improve the time complexity for the one-dimensional case from O(minK + n log2 n, n√K) for 0≤K≤n(n-1)/2 to O(n log K + K2) for K≤n. The latter is better when K≤√n log n. If we simply extend this result to the two-dimensional case, we will have the complexity of O(n3 log K + K2n2). We improve this complexity to O(n3) for K≤ √n.
Sung E. Bae Tadao Takaoka
Department of Computer Science and Software Engineering University of Canterbury, Christchurch, New Zealand
国际会议
The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)
昆明
英文
621-631
2005-08-01（万方平台首次上网日期，不代表论文的发表时间）