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:
- M₀ is a variable that receives zero at the beginning, right? But it is never called again... so what is happening here?
- 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? - The "max" part is something like a function? If that is so, doesn't it interfere with our algorithm Big-Oh notation?
- 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?