This answer describes a "double-ended" variant of Kadane that can be used as the basis for an algorithm with O(log n)-time updates. This variant is useful also for parallelization.
Recall that Kadane's algorithm maintains two quantities: max
(a.k.a. max_so_far
), the maximum subarray sum, and max_right
(a.k.a. max_ending_here
), the maximum sum of a subarray that extends from the right boundary. Double-ended Kadane computes two more quantities: max_left
, the maximum sum of a subarray that extends from the left boundary, and max_left_right
, the maximum sum of a subarray that extends from the left and right boundaries (i.e., the sum of the array). Store this information in the following structure.
struct KadaneResult {
int max;
int max_right;
int max_left;
int max_left_right;
};
Now given result structures for two arrays, we can compute a result structure for their concatenation. The correctness proof should be easy if you understand Kadane and I haven't screwed up :)
KadaneResult Combine(KadaneResult left, KadaneResult right) {
KadaneResult both;
both.max = maximum(left.max, right.max, left.max_right + right.max_left);
both.max_right = maximum(right.max_right, left.max_right + right.max_left_right);
both.max_left = maximum(left.max_left, left.max_left_right + right.max_left);
both.max_left_right = left.max_left_right + right.max_left_right;
return both;
}
For completeness, compute a result structure for zero and one elements.
KadaneResult Zero() {
KadaneResult zero;
zero.max = 0;
zero.max_right = 0;
zero.max_left = 0;
zero.max_left_right = 0;
return zero;
}
KadaneResult One(int x) {
KadaneResult one;
one.max = maximum(0, x);
one.max_right = maximum(0, x);
one.max_left = maximum(0, x);
one.max_left_right = x;
return x;
}
Now, put all of these result structures in a segment tree. Whenever you update one of the values at a leaf, recompute the result structures for its ancestors and read off the max
field at the root. As a practical optimization, if you detect that one of the recomputations had no effect, you can skip the subsequent ones for that update.