MAXIMUM SUBARRAY PROBLEM OPTIMIZATION FOR SPECIFIC DATA

Tomasz Rojek

trojek@pk.edu.pl
Cracow 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, optimization

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

Download


Published
2017-12-21

Cited by

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

Authors

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

Statistics

Abstract views: 195
PDF downloads: 242