1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – mlan
    May 5, 2021 at 10:15
  • $\begingroup$ 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. $\endgroup$
    – bigbang
    May 5, 2021 at 10:21
  • $\begingroup$ (Why not sum the whole array in the example for a sum of 4? Or exclude the last two elements…) $\endgroup$
    – greybeard
    May 5, 2021 at 11:07

1 Answer 1

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thank you, that helps a lot! $\endgroup$
    – mlan
    May 5, 2021 at 14:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.