Difference between revisions of "Maximum subvector sum"

From PEGWiki
Jump to: navigation, search
(Created page with "The '''maximum subvector sum''' problem is that of finding a segment of a vector (array of numbers)<ref>In computer science, ''vector'' is often used to mean ''array of real ...")
 
Line 1: Line 1:
The '''maximum subvector sum''' problem is that of finding a segment of a vector ([[array]] of numbers)<ref>In computer science, ''vector'' is often used to mean ''array of real numbers''; sometimes it is simply synonymous with ''array''. This meaning is related to but different from the meaning of the word in mathematics and physics.</ref>, possibly empty, with maximum sum. If all elements of the array are nonnegative, then the problem may be trivially solved by taking the entire vector; if all elements are negative, then the problem is again trivially solved by taking the empty segment (whose sum is [[Empty sum|conventionally defined to be zero]]). The problem requires more thought, however, when the vector contains a mixture of positive and negative numbers.
+
The '''maximum subvector sum''' problem is that of finding a segment of a vector ([[array]] of numbers)<ref>In computer science, ''vector'' is often used to mean ''array of real numbers''; sometimes it is simply synonymous with ''array''. Here, ''array'' is used in contradistinction with ''[[linked list]]'', which does not support efficient random access. This meaning is related to but different from the meaning of the word in mathematics and physics.</ref>, possibly empty, with maximum sum. If all elements of the array are nonnegative, then the problem may be trivially solved by taking the entire vector; if all elements are negative, then the problem is again trivially solved by taking the empty segment (whose sum is [[Empty sum|conventionally defined to be zero]]). The problem requires more thought, however, when the vector contains a mixture of positive and negative numbers.
 +
 
 +
This problem originated in the domain of image processing;<ref name="bentley">Bentley, Jon (1984), "Programming pearls: algorithm design techniques", ''Communications of the ACM'' '''27''' (9): 865–873, doi:10.1145/358234.381162.</ref> applications have also been found in data mining.<ref name="takaoka">Takaoka, T. (2002), "Efficient algorithms for the maximum subarray problem by distance matrix multiplication", ''Electronic Notes in Theoretical Computer Science'' '''61'''.</ref> In algorithmic programming competitions, Kadane's [[linear time]] algorithm for this problem is often useful as a building block within a more complex algorithm for processing a multidimensional array.
 +
 
 +
==One-dimensional problem==
 +
Bentley<ref name="bentley"/> describes four algorithms for this problem, of running time <math>O(n^3)</math>, <math>O(n^2)</math>, <math>O(n\log n)</math>, and <math>O(n)</math>. We discuss only the latter in this article, which is known as ''Kadane's algorithm'' after its discoverer.
 +
 
 +
Kadane's algorithm is a classic example of [[dynamic programming]]. It works by scanning the vector from left to right and computing the maximum-sum subvector ''ending at'' each of the vector's entries; denote the best sum ending at entry <math>i</math> by <math>M_i</math>. Also, for convenience, set <math>M_0 = 0</math> for the empty subvector. The maximum subvector sum for the entire array <math>A</math> is then, of course, <math>\max(M_0, M_1, M_2, \ldots, M_n)</math>. <math>M_i</math> for <math>i > 0</math> may then be computed as follows:
 +
:<math>M_i = \max(A_i, A_i + M_{i-1}) = A_i + \max(0, M_{i-1})</math>
 +
This formula is based on the following optimal substructure: The maximum-sum subvector ending at position <math>i</math> consists of either only the element <math>A_i</math> itself, or that element plus one or more elements <math>A_j, A_{j+1}, \ldots, A_{i-1}</math> (that is, ending at the previous position <math>i-1</math>). But the sum obtained in the latter case is simply <math>A_i</math> plus the sum of the subvector ending at <math>A_{i-1}</math>, so we want to make the latter as great as possible, requiring us to choose the maximum-sum subvector ending at <math>A_{i-1}</math>. This accounts for the <math>A_i + M_{i-1}</math> term. Of course, if <math>M_{i-1}</math> turned out to be negative, then there is no point in including any terms before <math>A_i</math> at all. This is why we must take the greater of <math>A_i</math> and <math>A_i + M_{i-1}</math>.
 +
 
 +
===Implementation (C++)===
 +
<syntaxhighlight lang="cpp">
 +
int max_subvector_sum(vector<int> V)
 +
{
 +
    int res = 0, cur = 0;
 +
    for (int i = 0; i < V.size(); i++)
 +
        res = max(res, cur = V[i] + max(0, cur));
 +
    return res;
 +
}
 +
</syntaxhighlight>
 +
 
 +
==Higher dimensions==
 +
The obvious generalization of the problem is as follows: given a <math>d</math>-dimensional array of dimensions <math>n_1 \geq n_2 \geq \ldots \geq n_d</math>, find indices <math>1 \leq a_1 \leq b_1 \leq n_1, 1 \leq a_2 \leq b_2 \leq n_2, \ldots, 1 \leq a_d \leq b_d \leq n_d</math> such that the sum <math>\sum_{i_1=a_1}^{b_1} \sum_{i_2=a_2}^{b_2} \ldots \sum_{i_d=a_d}^{b_d} A_{i_1, i_2, \ldots, i_d}</math> is maximized (or return 0 if all entries are negative). If we imagine a two-dimensional array as a matrix, then the problem is to pick some axis-aligned rectangle within the matrix with maximum sum.
 +
 
 +
There is a simple algorithm for this problem that runs in time <math>O(n_1 n_2^2 n_3^2 \ldots n_d^2)</math>. In the case with all dimensions equal, this reduces to <math>O(n^{2d-1})</math>, or <math>O(n^3)</math> in the two-dimensional case. The algorithm works by considering ''all possible'' sets of bounds <math>[a_2, b_2], [a_3, b_3], \ldots, [a_d, b_d]</math>; these number <math>O(n_2^2 n_3^2 \ldots n_d^2)</math>. For each such set of bounds, we compute <math>B_i = \sum_{i_2=a_2}^{b_2} \ldots \sum_{i_d=a_d}^{b_d} A_{i, i_2, \ldots, i_d}</math>. (We do this by building up the sum one index at a time using precomputed sums of boxes of lower dimension.) Then we find the one-dimensional max subvector sum in <math>B</math>, which takes linear time. The total time is then as stated.
 +
 
 +
This series of algorithms is not [[asymptotically optimal]]; for example, the <math>d=2</math> case can be solved in <math>O(n^3 (\log n)/(\log \log n))</math> time by a result due to Takaoka.<ref name="takaoka"/> In practice, however, the gains are not large.
 +
 
 +
==Problems==
 +
* {{Problem|monument|Baltic OI '09: Monument}}
 +
* {{Problem|wc02Sp1|WC '02: Dark Lord}}
  
 
==Notes and references==
 
==Notes and references==
 
<references/>
 
<references/>

Revision as of 21:21, 19 April 2012

The maximum subvector sum problem is that of finding a segment of a vector (array of numbers)[1], possibly empty, with maximum sum. If all elements of the array are nonnegative, then the problem may be trivially solved by taking the entire vector; if all elements are negative, then the problem is again trivially solved by taking the empty segment (whose sum is conventionally defined to be zero). The problem requires more thought, however, when the vector contains a mixture of positive and negative numbers.

This problem originated in the domain of image processing;[2] applications have also been found in data mining.[3] In algorithmic programming competitions, Kadane's linear time algorithm for this problem is often useful as a building block within a more complex algorithm for processing a multidimensional array.

One-dimensional problem

Bentley[2] describes four algorithms for this problem, of running time O(n^3), O(n^2), O(n\log n), and O(n). We discuss only the latter in this article, which is known as Kadane's algorithm after its discoverer.

Kadane's algorithm is a classic example of dynamic programming. It works by scanning the vector from left to right and computing the maximum-sum subvector ending at each of the vector's entries; denote the best sum ending at entry i by M_i. Also, for convenience, set M_0 = 0 for the empty subvector. The maximum subvector sum for the entire array A is then, of course, \max(M_0, M_1, M_2, \ldots, M_n). M_i for i > 0 may then be computed as follows:

M_i = \max(A_i, A_i + M_{i-1}) = A_i + \max(0, M_{i-1})

This formula is based on the following optimal substructure: The maximum-sum subvector ending at position i consists of either only the element A_i itself, or that element plus one or more elements A_j, A_{j+1}, \ldots, A_{i-1} (that is, ending at the previous position i-1). But the sum obtained in the latter case is simply A_i plus the sum of the subvector ending at A_{i-1}, so we want to make the latter as great as possible, requiring us to choose the maximum-sum subvector ending at A_{i-1}. This accounts for the A_i + M_{i-1} term. Of course, if M_{i-1} turned out to be negative, then there is no point in including any terms before A_i at all. This is why we must take the greater of A_i and A_i + M_{i-1}.

Implementation (C++)

int max_subvector_sum(vector<int> V)
{
    int res = 0, cur = 0;
    for (int i = 0; i < V.size(); i++)
        res = max(res, cur = V[i] + max(0, cur));
    return res;
}

Higher dimensions

The obvious generalization of the problem is as follows: given a d-dimensional array of dimensions n_1 \geq n_2 \geq \ldots \geq n_d, find indices 1 \leq a_1 \leq b_1 \leq n_1, 1 \leq a_2 \leq b_2 \leq n_2, \ldots, 1 \leq a_d \leq b_d \leq n_d such that the sum \sum_{i_1=a_1}^{b_1} \sum_{i_2=a_2}^{b_2} \ldots \sum_{i_d=a_d}^{b_d} A_{i_1, i_2, \ldots, i_d} is maximized (or return 0 if all entries are negative). If we imagine a two-dimensional array as a matrix, then the problem is to pick some axis-aligned rectangle within the matrix with maximum sum.

There is a simple algorithm for this problem that runs in time O(n_1 n_2^2 n_3^2 \ldots n_d^2). In the case with all dimensions equal, this reduces to O(n^{2d-1}), or O(n^3) in the two-dimensional case. The algorithm works by considering all possible sets of bounds [a_2, b_2], [a_3, b_3], \ldots, [a_d, b_d]; these number O(n_2^2 n_3^2 \ldots n_d^2). For each such set of bounds, we compute B_i = \sum_{i_2=a_2}^{b_2} \ldots \sum_{i_d=a_d}^{b_d} A_{i, i_2, \ldots, i_d}. (We do this by building up the sum one index at a time using precomputed sums of boxes of lower dimension.) Then we find the one-dimensional max subvector sum in B, which takes linear time. The total time is then as stated.

This series of algorithms is not asymptotically optimal; for example, the d=2 case can be solved in O(n^3 (\log n)/(\log \log n)) time by a result due to Takaoka.[3] In practice, however, the gains are not large.

Problems

Notes and references

  1. In computer science, vector is often used to mean array of real numbers; sometimes it is simply synonymous with array. Here, array is used in contradistinction with linked list, which does not support efficient random access. This meaning is related to but different from the meaning of the word in mathematics and physics.
  2. 2.0 2.1 Bentley, Jon (1984), "Programming pearls: algorithm design techniques", Communications of the ACM 27 (9): 865–873, doi:10.1145/358234.381162.
  3. 3.0 3.1 Takaoka, T. (2002), "Efficient algorithms for the maximum subarray problem by distance matrix multiplication", Electronic Notes in Theoretical Computer Science 61.