Editing Maximum subvector sum
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>. | ||
− | |||
− | |||
− | |||
===Implementation (C++)=== | ===Implementation (C++)=== | ||
− | |||
<syntaxhighlight lang="cpp"> | <syntaxhighlight lang="cpp"> | ||
− | + | int max_subvector_sum(vector<int> V) | |
− | int max_subvector_sum( | + | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
{ | { | ||
int res = 0, cur = 0; | int res = 0, cur = 0; | ||
Line 41: | Line 22: | ||
==Higher dimensions== | ==Higher dimensions== | ||
− | The obvious generalization of the problem is as follows: given a <math>d</math>-dimensional array | + | 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. | |
− | + | ||
− | The | + | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | 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== | ==Problems== |