How can we represent a function which outputs the running max in mathematical notation?
I am under the impression that this sort of functions are not, strictly speaking, mathematical functions because at each item of the domain can correspond more than one item in the codomain. Even so, I wonder whether there is a mathematical notation to describe it.
e.g.:
Input | Output
0 0
1 | 1
3 | 3
2 | 3
0 | 3
5 | 5
1 | 5
-4 | 5
Best Answer
Let $\{x_k\}$ be some sequence of elements from some ordered set (say $\mathbb{R}$). Then for any $n \in \mathbb{N}$, the largest element of the sequence with index less than or equal to $n$ is given by $$ \max\{ x_k \mid k \le n\} = \max\{ x_1, x_2, \dotsc, x_n\}. $$ The following feels like overkills to me, but if this is an object which is going to be used over and over again, it might be useful to introduces a little extra notation. For example, suppose that $X$ is some ordered set (such as $\mathbb{R}$). The set of all sequences consisting of elements of $X$ is denoted by $X^{\mathbb{N}}$. So we might define $$ M : \mathbb{N} \times X^{\mathbb{N}} \to X : \bigl(n,\{x_k\}\bigr) \mapsto \max\{ x_k \mid k\le n\}. $$ $M$ is then a function which takes as input a natural number (an index) and some sequence in $X$, and returns the largest element of that sequence with index less than or equal to $n$. In the example given in the question, $$ M(4, \{ 0, 1, 3, 2, 0, 5, 1, -4, \dotsc \} ) = 3. $$
If the sequence $\{x_k\}$ is fixed, then Alec B-G's suggestion is also reasonable. Thinking of the function $M$ as a function from $\mathbb{N}$ to $X$ (that is, as a sequence of elements of $X$), we could write $$ M_n = \max\{ x_k \mid k \le n\}. $$ Finally, from a computational standpoint, it might be more efficient to define $M_n = \max\{ M_{n-1}, x_n\}$.