Editing Maximum subvector sum

Jump to: navigation, search

Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.

The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision Your text
Line 9: Line 9:
 
:<math>M_i = \max(A_i, A_i + M_{i-1}) = A_i + \max(0, M_{i-1})</math>
 
:<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>.
 
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>.
 
===Example===
 
In the vector [5, -3, -3, 3, 0, -1, 4, -5, 5], the maximal subvector is [3, 0, -1, 4]; this subvector has a sum of 6, which is greater than that of any other subvector. Notice that in order to construct this subvector, we had to take a negative entry because it lay between two large positive entries; if we refused to include any negative entries, the maximum sum obtainable would be only 5 (by taking one of the elements at the ends).
 
  
 
===Implementation (C++)===
 
===Implementation (C++)===
Line 45: Line 42:
 
We describe a simple algorithm for this problem. It works by recursively reducing a <math>d</math>-dimensional problem to <math>O(n_1^2)</math> simpler, <math>(d-1)</math>-dimensional problems, terminating at <math>d=1</math> which can be solved in <math>O(n_d)</math> time using the one-dimensional algorithm. Evidently, this algorithm takes time <math>O(n_1^2 n_2^2 \ldots n_{d-1}^2 n_d)</math>. In the case with all dimensions equal, this reduces to <math>O(n^{2d-1})</math>.
 
We describe a simple algorithm for this problem. It works by recursively reducing a <math>d</math>-dimensional problem to <math>O(n_1^2)</math> simpler, <math>(d-1)</math>-dimensional problems, terminating at <math>d=1</math> which can be solved in <math>O(n_d)</math> time using the one-dimensional algorithm. Evidently, this algorithm takes time <math>O(n_1^2 n_2^2 \ldots n_{d-1}^2 n_d)</math>. In the case with all dimensions equal, this reduces to <math>O(n^{2d-1})</math>.
  
The details are as follows. We try all possible sets of bounds <math>[a_1, b_1] \subseteq [1, n_1]</math> for the first index. For each such interval, we create a <math>(d-1)</math>-dimensional tensor <math>B</math> where <math>B_{i_2, i_3, \ldots, i_d} = \sum_{i_1=a_1}^{b_1} A_{i_1, i_2, \ldots, i_d}</math> and compute the maximum subtensor sum in <math>B</math>. The range of indices that this represents in the original array will be the Cartesian product of the indices in the maximum-sum subtensor of <math>B</math> and the original range <math>[a_1, b_1]</math>, so that by trying all possibilities for the latter, we will account for all possible subtensors of the original array <math>A</math>.
+
The details are as follows. We try all possible sets of bounds <math>[a_1, b_1] \in [1, n_1]</math> for the first index. For each such interval, we create a <math>(d-1)</math>-dimensional tensor <math>B</math> where <math>B_{i_2, i_3, \ldots, i_d} = \sum_{i_1=a_1}^{b_1} A_{i_1, i_2, \ldots, i_d}</math> and compute the maximum subtensor sum in <math>B</math>. The range of indices that this represents in the original array will be the Cartesian product of the indices in the maximum-sum subtensor of <math>B</math> and the original range <math>[a_1, b_1]</math>, so that by trying all possibilities for the latter, we will account for all possible subtensors of the original array <math>A</math>.
  
===Two-dimensional implementation===
+
===Two-dimensional example===
 
In two dimensions, the time required is <math>O(m^2 n)</math>, where <math>m < n</math>, or <math>O(n^3)</math> if <math>m = n</math>. 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. The algorithm described above can be written as follows:
 
In two dimensions, the time required is <math>O(m^2 n)</math>, where <math>m < n</math>, or <math>O(n^3)</math> if <math>m = n</math>. 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. The algorithm described above can be written as follows:
 
<syntaxhighlight lang="cpp">
 
<syntaxhighlight lang="cpp">

Please note that all contributions to PEGWiki are considered to be released under the Attribution 3.0 Unported (see PEGWiki:Copyrights for details). If you do not want your writing to be edited mercilessly and redistributed at will, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource. Do not submit copyrighted work without permission!

Cancel | Editing help (opens in new window)

Templates used on this page: