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