1
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ The notation is cumbersome. $M_t$ represents a finite sequence of numbers, and could as well have been represented as array elements $M[t]$. The $\max$ function works in constant time. The loops do not talk to each other, the second is executed after the first. $\endgroup$
    – user16034
    Sep 22, 2022 at 7:22
  • $\begingroup$ @YvesDaoust Yes, I think the same. I'm trying to "translate" that pseudo-code to Python, but no success. It's not written in pseudocode only, some parts are in "mathematical" language. $\endgroup$ Sep 22, 2022 at 22:01
  • 1
    $\begingroup$ Can you say what doesn't work with Yves Daoust's solution? You just need to declare $M$ as an array of values indexed from $0$ to $n$ (let's say, initialized with $0$'s), and replace $M_0$ by $M[0]$ and every $M_t$ by $M[t]$. And adjust the fact that $A$ will be indexed from $0$ to $n - 1$ in python. $\endgroup$ Sep 22, 2022 at 23:39

1 Answer 1

0
$\begingroup$

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
$\endgroup$

Your Answer

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

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