In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, the maximum sum subarray problem, also known as the maximum segment sum problem, is the task of finding a contiguous subarray with the largest sum, within a given one-dimensional
array
An array is a systematic arrangement of similar objects, usually in rows and columns.
Things called an array include:
{{TOC right
Music
* In twelve-tone and serial composition, the presentation of simultaneous twelve-tone sets such that the ...
A
...nof numbers. Formally, the task is to find indices
and
with
, such that the sum
:
is as large as possible. (Some formulations of the problem also allow the empty subarray to be considered; by convention,
the sum of all values of the empty subarray is zero.) Each number in the input array A could be positive, negative, or zero.
For example, for the array of values
minus;2, 1, −3, 4, −1, 2, 1, −5, 4 the contiguous subarray with the largest sum is
, −1, 2, 1 with sum 6.
Some properties of this problem are:
# If the array contains all non-negative numbers, then the problem is trivial; a maximum subarray is the entire array.
# If the array contains all non-positive numbers, then a solution is any subarray of size 1 containing the maximal value of the array (or the empty subarray, if it is permitted).
# Several different sub-arrays may have the same maximum sum.
This problem can be solved using several different algorithmic techniques, including brute force, divide and conquer, dynamic programming, and reduction to shortest paths.
History
The maximum subarray problem was proposed by
Ulf Grenander
Ulf Grenander (23 July 1923 – 12 May 2016) was a Swedish statistician and professor of applied mathematics at Brown University.
His early research was in probability theory, stochastic processes, time series analysis, and statistical theory (p ...
in 1977 as a simplified model for
maximum likelihood estimation
In statistics, maximum likelihood estimation (MLE) is a method of estimating the parameters of an assumed probability distribution, given some observed data. This is achieved by maximizing a likelihood function so that, under the assumed statis ...
of patterns in digitized images.
Grenander was looking to find a rectangular subarray with maximum sum, in a two-dimensional array of real numbers. A brute-force algorithm for the two-dimensional problem runs in ''O''(''n''
6) time; because this was prohibitively slow, Grenander proposed the one-dimensional problem to gain insight into its structure. Grenander derived an algorithm that solves the one-dimensional problem in ''O''(''n''
2) time,
improving the brute force running time of ''O''(''n''
3). When
Michael Shamos heard about the problem, he overnight devised an ''O''(''n'' log ''n'')
divide-and-conquer algorithm
In computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved dire ...
for it.
Soon after, Shamos described the one-dimensional problem and its history at a
Carnegie Mellon University
Carnegie Mellon University (CMU) is a private research university in Pittsburgh, Pennsylvania. One of its predecessors was established in 1900 by Andrew Carnegie as the Carnegie Technical Schools; it became the Carnegie Institute of Technology ...
seminar attended by
Jay Kadane, who designed within a minute an ''O''(''n'')-time algorithm, which is as fast as possible.
[since every algorithm must at least scan the array once which already takes ''O''(''n'') time] In 1982,
David Gries
David Gries (born April 26, 1939 in Flushing, Queens, New York) is an American computer scientist at Cornell University, United States mainly known for his books ''The Science of Programming'' (1981) and ''A Logical Approach to Discrete Math'' ( ...
obtained the same ''O''(''n'')-time algorithm by applying
Dijkstra's "standard strategy"; in 1989,
Richard Bird derived it by purely algebraic manipulation of the brute-force algorithm using the
Bird–Meertens formalism.
Grenander's two-dimensional generalization can be solved in O(''n''
3) time either by using Kadane's algorithm as a subroutine, or through a divide-and-conquer approach. Slightly faster algorithms based on
distance matrix multiplication have been proposed by and by . There is some evidence that no significantly faster algorithm exists; an algorithm that solves the two-dimensional maximum subarray problem in O(''n''
3−ε) time, for any ε>0, would imply a similarly fast algorithm for the
all-pairs shortest paths problem.
Applications
Maximum subarray problems arise in many fields, such as genomic
sequence analysis
In bioinformatics, sequence analysis is the process of subjecting a DNA, RNA or peptide sequence to any of a wide range of analytical methods to understand its features, function, structure, or evolution. Methodologies used include sequence alignm ...
and
computer vision
Computer vision is an interdisciplinary scientific field that deals with how computers can gain high-level understanding from digital images or videos. From the perspective of engineering, it seeks to understand and automate tasks that the hum ...
.
Genomic sequence analysis employs maximum subarray algorithms to identify important biological segments of protein sequences. These problems include conserved segments, GC-rich regions, tandem repeats, low-complexity filter, DNA binding domains, and regions of high charge.
In
computer vision
Computer vision is an interdisciplinary scientific field that deals with how computers can gain high-level understanding from digital images or videos. From the perspective of engineering, it seeks to understand and automate tasks that the hum ...
, maximum-subarray algorithms are used on bitmap images to detect the brightest area in an image.
Kadane's algorithm
Empty subarrays admitted
Kadane's original algorithm solves the problem version when empty subarrays are admitted. It scans the given array