MAXIMUM SUBARRAY PROBLEM OPTIMIZATION FOR SPECIFIC DATA
Tomasz Rojek
trojek@pk.edu.plCracow University of Technology, Faculty of Mechanical Engineering, Institute of Applied Informatics (Poland)
Abstract
The maximum subarray problem (MSP) is to the find maximum contiguous sum in an array. This paper describes a method of Kadanes algorithm (the state of the art) optimization for specific data (continuous sequences of zeros or negative real numbers). When the data are unfavourable, the modification of the algorithm causes a non significant performance loss (1% > decrease in performance). The modification does not improve time complexity but reduces the number of elementary operations. Various experimental data sets have been used to evaluate possible time efficiency improvement. For the most favourable data sets an increase in efficiency of 25% can be achieved.
Keywords:
Algorithm design and analysis, maximum subarray problem, Kadane’s algorithm, optimizationReferences
Lloyd A.: Longest biased interval and longest non-negative sum interval. Bioinformatics 19, 2003, 1294–1295.
Google Scholar
Bae Sung Eun: Sequential and Parallel Algorithms for the Generalized Maximum Subarray Problem. Ph.D. Thesis, University of Canterbury, 2007.
Google Scholar
Bentley J.: Programming pearls: algorithm design techniques. Communications of the ACM, 27(9), 1984, 865–873.
Google Scholar
BT Series Broadcasting. Parameter values for the HDTV standards for production and international programme exchange BT Series Broadcasting service – volume 5, 2002.
Google Scholar
Grenander U.: Pattern analysis. Springer, 1978.
Google Scholar
Huang X.: An algorithm for identifying regions of a DNA sequence that satisfy a content requirement. Computer applications in the biosciences: CABIOS 10, 1994, 219–225.
Google Scholar
Larson R. C., Odoni A. R.: Urban operations research. Prentice-Hall, New Jersey 1981.
Google Scholar
Lin Yaw Ling, Jiang Tao, Chao Kun Mao: Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis. Journal of Computer and System Sciences 65, 2003, 570–586.
Google Scholar
Perumalla K., Deo N.: Parallel algorithms for maximum subsequence and maximum subarray. Parallel Processing Letters 5(03), 1995, 367–373.
Google Scholar
Tokyo IBM: Data Association Mining Rules: Using Algorithms, Optimized and Scheme, Visualization, 1996.
Google Scholar
Wang L., Xu Ying: SEGID: Identifying interesting segments in (multiple) sequence alignments. Bioinformatics 19, 297–298, 2003.
Google Scholar
Authors
Tomasz Rojektrojek@pk.edu.pl
Cracow University of Technology, Faculty of Mechanical Engineering, Institute of Applied Informatics Poland
Statistics
Abstract views: 191PDF downloads: 240
License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
