Kadaneti

The maximum subarray problem was proposed by Ulf Grenander in 1977 as a simplified model for
maximum likelihood estimation of patterns in digitized images.[5]
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(n6) 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(n2) time,[note
1] improving the brute force running time of O(n3). When Michael Shamos heard about the problem, he
overnight devised an O(n log n) divide-and-conquer algorithm for it. Soon after, Shamos described the
one-dimensional problem and its history at a Carnegie Mellon University seminar attended by Jay
Kadane, who designed within a minute an O(n)-time algorithm,[5][6][7] which is as fast as possible.[note
2] In 1982, David Gries obtained the same O(n)-time algorithm by applying Dijkstra's "standard strategy";
[8] in 1989, Richard Bird derived it by purely algebraic manipulation of the brute-force algorithm using
the Bird–Meertens formalism.[9]
Grenander's two-dimensional generalization can be solved in O(n3) 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 Tamaki & Tokuyama (1998) and by Takaoka
(2002). There is some evidence that no significantly faster algorithm exists; an algorithm that solves the
two-dimensional maximum subarray problem in O(n3−ε) time, for any ε>0, would imply a similarly fast
algorithm for the all-pairs shortest paths problem.[10]
Applications
This section needs attention from an expert in Computational biology. The specific problem is: fix inline
tags. WikiProject Computational biology may be able to help recruit an expert. (September 2019)
Maximum subarray problems arise in many fields, such as genomic sequence analysis and computer
vision.
Genomic sequence analysis employs maximum subarray algorithms to identify important biological
segments of protein sequences.[citation needed] These problems include conserved segments, GC-rich
regions, tandem repeats, low-complexity filter, DNA binding domains, and regions of high charge.
[citation needed]
In computer vision, maximum-subarray algorithms are used on bitmap images to detect the brightest
area in an image.
Kadane's algorithm
No empty subarrays admitted
Kadane's algorithm scans the given array
{\displaystyle A[1\ldots n]} from left to right. In the
{\displaystyle j}th step, it computes the subarray with the largest sum ending at
{\displaystyle j}; this sum is maintained in variable current_sum.[note 3] Moreover, it computes the
subarray with the largest sum anywhere in
{\displaystyle A[1\ldots j]}, maintained in variable best_sum,[note 4] and easily obtained as the
maximum of all values of current_sum seen so far, cf. line 7 of the algorithm.
As a loop invariant, in the
{\displaystyle j}th step, the old value of current_sum holds the maximum over all
{\displaystyle i\in \{1,\ldots ,j-1\}} of the sum
−
1
{\displaystyle A[i]+\cdots +A[j-1]}. Therefore, current_sum
{\displaystyle +A[j]}[note 5] is the maximum over all
{\displaystyle i\in \{1,\ldots ,j-1\}} of the sum
+
⋯
{\displaystyle A[i]+\cdots +A[j]}. To extend the latter maximum to cover also the case
{\displaystyle i=j}, it is sufficient to consider also the singleton subarray
{\displaystyle A[j\;\ldots \;j]}. This is done in line 6 by assigning
max
{\displaystyle \max(A[j],}current_sum
+
{\displaystyle +A[j])} as the new value of current_sum, which after that holds the maximum over all
{\displaystyle i\in \{1,\ldots ,j\}} of the sum
[
𝑗
{\displaystyle A[i]+\cdots +A[j]}.
Thus, the problem can be solved with the following code,[11] expressed in Python.
def max_subarray(numbers):
"""Find the largest sum of any contiguous subarray."""
best_sum = - infinity
current_sum = 0
for x in numbers:
current_sum = max(x, current_sum + x)
best_sum = max(best_sum, current_sum)
return best_sum
If the input contains no positive element, the returned value is that of the largest element (i.e., the value
closest to 0), or negative infinity if the input was empty. For correctness, an exception should be raised
when the input array is empty, since an empty array has no maximum nonempty subarray. If the array is
nonempty, its first element could be used in place of negative infinity, if needed to avoid mixing numeric
and non-numeric values.
The algorithm can be adapted to the case which allows empty subarrays or to keep track of the starting
and ending indices of the maximum subarray.
This algorithm calculates the maximum subarray ending at each position from the maximum subarray
ending at the previous position, so it can be viewed as a trivial case of dynamic programming.
Empty subarrays admitted
Example run
Kadane's original algorithm solves the problem variant when empty subarrays are admitted.[4][7] This
variant will return 0 if the input contains no positive elements (including when the input is empty). It is
obtained by two changes in code: in line 3, best_sum should be initialized to 0 to account for the empty
subarray
{\displaystyle A[0\ldots -1]}

Kadaneti

Uploaded by

Copyright:

Available Formats

Kadaneti

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Kadaneti

Uploaded by

Copyright:

Available Formats

The maximum subarray problem was proposed by Ulf Grenander in 1977 as a simplified model for

maximum likelihood estimation of patterns in digitized images.[5]

No empty subarrays admitted

Kadane's algorithm scans the given array

{\displaystyle A[1\ldots n]} from left to right. In the

{\displaystyle i\in \{1,\ldots ,j-1\}} of the sum

{\displaystyle A[i]+\cdots +A[j-1]}. Therefore, current_sum

{\displaystyle +A[j]}[note 5] is the maximum over all

{\displaystyle i\in \{1,\ldots ,j-1\}} of the sum

{\displaystyle i=j}, it is sufficient to consider also the singleton subarray

{\displaystyle A[j\;\ldots \;j]}. This is done in line 6 by assigning

{\displaystyle i\in \{1,\ldots ,j\}} of the sum

{\displaystyle A[i]+\cdots +A[j]}.

"""Find the largest sum of any contiguous subarray."""

current_sum = max(x, current_sum + x)

best_sum = max(best_sum, current_sum)

Empty subarrays admitted

{\displaystyle A[0\ldots -1]}

You might also like