How to solve this max contiguous subarray sum with a twist?

Question

How to solve the max contiguous subarray problem, where we have an addition parameter $M$, and the contiguous subarray must include both $A[M]$ and $A[M-1]$?

For example, for the zero-indexed array $1, -4, 2, -2, 4, 1, -1, 1$, if $M=1$ then the contiguous subarray must include the first two elements, and so the answer is $-1$ (corresponding to the contiguous subarray $1,-4,2$).

The code I have right now without this "twist" is:

procedure MaxSubarraySum(A):
    current_sum <- 0
    max_sum <- (-infinity)
    N <- A.length
    for i <- 0 to N do:
        current_sum <- current_sum + A[i]
        if current_sum > max_sum then:
            max_sum <- current_sum
        endif
        if current_sum < 0 then:
            current_sum <- 0
        endif
    endfor
    
    return max_sum

But I'm stuck on how to change it so that max_sum always include $A[M]$ and $A[M - 1]$.

Answer 1

Let the input array be $A[1 \dots n]$ and consider any contiguous subarray $A[i \dots j]$ of $A$ such that $i \le M-1$ and $j \ge M$ (that is, $A[i \dots, j]$ includes both $A[M-1]$ and $A[M]$).

The subarray $A[i \dots j]$ maximizes $\sum_{k=i}^j A[k]$ if and only if:

1. $A[i,\dots M-2]$ is a (possibly empty) suffix of $A[1 \dots, M-2]$ that maximizes $\sum_{k=i}^{M-2} A[k]$;
2. $A[M+1,\dots j]$ is a (possibly empty) prefix of $A[M+1 \dots,n]$ that maximizes $\sum_{k=M+1}^{j} A[k]$.

This is easy to prove using a cut-and-paste argument. Notice that 1. and 2. are essentially the same problem, which can be solved by a trivial $O(n)$-time algorithm that computes the sum of all prefixes/suffxes of $A$.