Updating maximum sum subinteral in an array in sublinear time when an adjacent transposition is applied

Question

I asked this question for general transpositions and it seemed too hard, I only got one answer which didn't seem to give a guaranteed asymptotic speed-up. So suppose we apply a sequence of adjacent transpositions to a numeric array (an adjacent transposition swaps two adjacent numbers) and we want to maintain the solution of the maximum sum subinterval after each adjacent transposition. We could repeat Kadane's linear time solution from scratch on the entire array after every adjacent transposition. So that is what I want to beat. Can this be done in sublinear time per adjacent transposition, say if we do N or N^2 adjacent transpositions for an array of size N, and we are allowed to do preprocessing as long as the amortized preprocessing time is sublinear for the entire set of applied transpositions?

Answer 1

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.