MAXIMUM SUBARRAY PROBLEM OPTIMIZATION FOR SPECIFIC DATA


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; optimization

Lloyd A.: Longest biased interval and longest non-negative sum interval. Bioinformatics 19, 2003, 1294–1295.

Bae Sung Eun: Sequential and Parallel Algorithms for the Generalized Maximum Subarray Problem. Ph.D. Thesis, University of Canterbury, 2007.

Bentley J.: Programming pearls: algorithm design techniques. Communications of the ACM, 27(9), 1984, 865–873.

BT Series Broadcasting. Parameter values for the HDTV standards for production and international programme exchange BT Series Broadcasting service – volume 5, 2002.

Grenander U.: Pattern analysis. Springer, 1978.

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.

Larson R. C., Odoni A. R.: Urban operations research. Prentice-Hall, New Jersey 1981.

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.

Perumalla K., Deo N.: Parallel algorithms for maximum subsequence and maximum subarray. Parallel Processing Letters 5(03), 1995, 367–373.

Tokyo IBM: Data Association Mining Rules: Using Algorithms, Optimized and Scheme, Visualization, 1996.

Wang L., Xu Ying: SEGID: Identifying interesting segments in (multiple) sequence alignments. Bioinformatics 19, 297–298, 2003.

Download

Published : 2017-12-21


Rojek, T. (2017). MAXIMUM SUBARRAY PROBLEM OPTIMIZATION FOR SPECIFIC DATA. Informatyka, Automatyka, Pomiary W Gospodarce I Ochronie Środowiska, 7(4), 62-65. https://doi.org/10.5604/01.3001.0010.7507

Tomasz Rojek  trojek@pk.edu.pl
Cracow University of Technology, Faculty of Mechanical Engineering, Institute of Applied Informatics  Poland