Algorithms for the Problem of K Maximum Sums and a VLSI Algorithm for the K Maximum Subarrays Problem

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Sung Eun Bae Articles by Tadao Takaoka

2004 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN'04)

Hong Kong, SAR, China

May 10-May 12

ISBN: 0-7695-2135-5

	ASCII Text	x
	Sung Eun Bae, Tadao Takaoka, "Algorithms for the Problem of K Maximum Sums and a VLSI Algorithm for the K Maximum Subarrays Problem," Parallel Architectures, Algorithms, and Networks, International Symposium on, pp. 247, 2004 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN'04), 2004.

	BibTex	x
	@article{ 10.1109/ISPAN.2004.1300488, author = {Sung Eun Bae and Tadao Takaoka}, title = {Algorithms for the Problem of K Maximum Sums and a VLSI Algorithm for the K Maximum Subarrays Problem}, journal ={Parallel Architectures, Algorithms, and Networks, International Symposium on}, volume = {0}, year = {2004}, issn = {1087-4089}, pages = {247}, doi = {http://doi.ieeecomputersociety.org/10.1109/ISPAN.2004.1300488}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Parallel Architectures, Algorithms, and Networks, International Symposium on TI - Algorithms for the Problem of K Maximum Sums and a VLSI Algorithm for the K Maximum Subarrays Problem SN - 1087-4089 SP EP A1 - Sung Eun Bae, A1 - Tadao Takaoka, PY - 2004 KW - maximum subarray KW - maximum subsequence KW - prefix sums KW - VLSI VL - 0 JA - Parallel Architectures, Algorithms, and Networks, International Symposium on ER -

Sung Eun Bae, University of Canterbury, Christchurch, New Zealand

Tadao Takaoka, University of Canterbury, Christchurch, New Zealand

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISPAN.2004.1300488

Given an array of positive and negative values, we consider the problem of K maximum sums. When an overlapping property needs to be observed, previous algorithms for the maximum sum are not directly applicable. We designed an O(K * n) algorithm for the K maximum subsequences problem. This was then modified to solve the K maximum subarrays problem in O(K * n{3}) time. Finally, we present a VLSI K maximum subarrays algorithm with O(K * n) steps and a circuit size of O(n{2}), which is cost-optimal in parallelisation of the sequential algorithm.

Index Terms:

maximum subarray, maximum subsequence, prefix sums, VLSI

Citation:

Sung Eun Bae, Tadao Takaoka, "Algorithms for the Problem of K Maximum Sums and a VLSI Algorithm for the K Maximum Subarrays Problem," ispan, pp.247, 2004 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN'04), 2004

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.