# 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 "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]$$.

• I understand the last part of your solution, starting from A[m + 1] and incrementing until A[n] as long as A[i] is positive. Is the first part just the same except you go the opposite direction?
– mlan
May 5, 2021 at 10:15
• You see that you have to have $A[m-1]$ and $A[m]$ in your sub-array. So what you need is to have the suffix of $A[1\ldots m-2]$ which has the maximum sum, and similarly, you need the prefix of $A[m+1 \ldots n]$ which has the maximum sum. Note that, these prefix and suffix may be empty. May 5, 2021 at 10:21
• (Why not sum the whole array in the example for a sum of 4? Or exclude the last two elements…) May 5, 2021 at 11:07

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