How can I convert the pseudo-code that solves maximum subarray problem to Python code?

Question

I'm reading Algorithm Design and Application, by Michael T. Goodrich and Robert Tamassia, and sometimes the pseudo-code in this book doesn't make sense at all.

At chapter one they show us 3 solutions for the famous maximum subarray problem. I understood completely the first and second solutions, but the third one (the fastest) seems impossible to understand.

The pseudo-code for this solution is this:

Algorithm MaxsubFastest(A):
    Input: An n-element array A of numbers, indexed from 1 to n.
    Output: The maximum subarray sum of array A.

   M₀ ← 0    // the initial prefix maximum
   for t ← 1 to n do
      Mₜ ← max{0, Mₜ₋₁ + A[t]}
   
   m ← 0    // the maximum found so far
   for t ← 1 to n do
      m ← max{m, Mₜ }

   return m

What I don't get about this pseudo-code is this:

1. M₀ is a variable that receives zero at the beginning, right? But it is never called again... so what is happening here?
2. How the Mₜ ← max{0, Mₜ₋₁ + A[t]} part works at all? Is it creating a lot of Mₜ variables, one for every t value?
3. The "max" part is something like a function? If that is so, doesn't it interfere with our algorithm Big-Oh notation?
4. There are two loops that seems to "talk" to each other, otherwise they run separately.

I think that a good way to end my questioning is to see this code in a programming language I know (Javascript or Python, preferably). So, my question: how can I implement this pseudo-code in Python?

Answer 1

How the $M_t ← \max\{0, M_{t-1} + A[t]\}$ part works at all? Is it creating a lot of $M_t$ variables, one for every t value?

Yes, it is creating variable $M_t$ for every $t$. Together with $M_0$, there are $n+1$ of them.

When $t=1$, the statement is $M_1 ← \max\{0, M_0 + A[1]\}$. Note that $M_0$ is used.

The "max" part is something like a function? If that is so, doesn't it interfere with our algorithm Big-Oh notation?

Yes, $\max$ is a function of two numbers that returns the bigger one between the two numbers or anyone of them if they are equal.

It is assumed that it takes up to to some constant time to call that function. A constant factor does not affect the big-$O$ notation.

There are two loops that seems to "talk" to each other, otherwise they run separately.

Yes. The first loop creates/computes a list of $M_t$. The second loop finds the maximum of them.

---

Here is corresponding code in Python. Note that the code uses $A[t-1]$ instead of $A[t]$ in the pseudocode since the index starts from $0$ in Python instead of $1$ in the pseudocode.

def MaxsubFastest(A):
    """Return the maximum sum of a subarray of A """
    n = len(A)
    M = [-1] * (n + 1)  # -1 stands for not set.
    M[0] = 0
    for t in range(1, n + 1):
        M[t] = max(0, M[t - 1] + A[t - 1])
    m = 0
    for t in range(1, n + 1):
        m = max(m, M[t])
    return m

---

As you might have suspected, we can reduce the usage of $n+1$ $M_t$'s to only only variable $b$, which will be the bigger one between 0 and the maximum sum of a subarray that ends at current index of $A$. To enable that, we will merge two loops into one, keeping $m$ as the maximum sum of a subarray that have considered so far.

def MaxsubFastestWithLeastSpace(A):
    """Return the maximum sum of a subarray of A """
    c = 0
    m = 0
    for t in range(1, len(A) + 1):
        # c is the maximum sum of a subarray that ends at index t-1
        # if that sum is greater than 0; otherwise c is 0.
        c = max(0, c + A[t - 1])
        # the maximum sum of a subarray that ends before index t
        m = max(m, c)
    return m