How to solve this max contiguous subarray sum with a twist? 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 &quot;twist&quot; is:
procedure MaxSubarraySum(A):
    current_sum &lt;- 0
    max_sum &lt;- (-infinity)
    N &lt;- A.length
    for i &lt;- 0 to N do:
        current_sum &lt;- current_sum + A[i]
        if current_sum &gt; max_sum then:
            max_sum &lt;- current_sum
        endif
        if current_sum &lt; 0 then:
            current_sum &lt;- 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]$.
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:

$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]$;
$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$.