Probably the best possible, in any case a matrix with $O(n^3)$ turning points, is $$\begin{pmatrix} 1&1&\dots&&&\color{red}1&2\\ \vdots&\vdots&&&\!\!\!\color{red}{ {_{\displaystyle \raise -3pt\cdot}\displaystyle\cdot \,^{\displaystyle \cdot}}}&\color{red}2&3\\ \vdots&\vdots&&& \!\!\! \color{red}{ {_{\displaystyle \raise -3pt \cdot}\displaystyle\cdot\, ^{\displaystyle \cdot}}} &\color{red} \vdots& \vdots \\ 1&1&\dots &&&\color{red}{n-1} &n\\ 1&1&\dots &&\!\!\!\!\color{red}{n-1} &n&n\\ \vdots&\color{red}{ {_{\displaystyle\raise -3pt \cdot}\displaystyle\cdot \,^{\displaystyle \cdot}}}&\color{red}{ {_{\displaystyle \raise -3pt\cdot}\displaystyle\cdot \,^{\displaystyle \cdot}}}&&& \vdots & \vdots \\ \color{red}1&\color{red}2&\dots&&&n & n \\ 2&3&\dots&&&n & n \\ \end{pmatrix}$$ with constant antidiagonals, which has $\displaystyle \sum_{i=1}^{n-1}(n^2-i)=n^3-n-\frac{n(n-1)}2=O(n^3)$ turning points (in red). Or am I missing something?
(BTW is there a Latex command for rising \ddots?)

Probably the best possible, in any case a matrix with $O(n^3)$ turning points, is $$\begin{pmatrix} 1&1&\dots&&&\color{red}1&2\\ \vdots&\vdots&&&\!\!\!\color{red}{ {_{\displaystyle \raise -3pt\cdot}\displaystyle\cdot \,^{\displaystyle \cdot}}}&\color{red}2&3\\ \vdots&\vdots&&& \!\!\! \color{red}{ {_{\displaystyle \raise -3pt \cdot}\displaystyle\cdot\, ^{\displaystyle \cdot}}} &\color{red} \vdots& \vdots \\ 1&1&\dots &&&\color{red}{n-1} &n\\ 1&1&\dots &&\!\!\!\!\color{red}{n-1} &n&n\\ \vdots&\color{red}{ {_{\displaystyle\raise -3pt \cdot}\displaystyle\cdot \,^{\displaystyle \cdot}}}&\color{red}{ {_{\displaystyle \raise -3pt\cdot}\displaystyle\cdot \,^{\displaystyle \cdot}}}&&& \vdots & \vdots \\ \color{red}1&\color{red}2&\dots&&&n & n \\ 2&3&\dots&&&n & n \\ \end{pmatrix}$$ with constant antidiagonals, which has $\displaystyle \sum_{i=1}^{n-1}(n^2-i)=n^3-n^2-\frac{n(n-1)}2=O(n^3)$ turning points (in red). Or am I missing something?
(BTW is there a Latex command for rising \ddots?)

Trivially, best possible is $$\begin{pmatrix} 1&1&\dots&&1&2\\ \vdots&&&&2&3\\ \vdots&&&& \vdots & \vdots \\ 1&1&\dots &&n-1 &n\\ 1&1&\dots &n-1 &n&n\\ \vdots&&&& \vdots & \vdots \\ n&n&\dots&&n & n \\ \end{pmatrix}$$ with constant antidiagonals, which has $(n-1)(n^2-1)=O(n^3)$ turning points. Or am I missing something?
(BTW is there a Latex command for rising \ddots?)

Probably the best possible, in any case a matrix with $O(n^3)$ turning points, is $$\begin{pmatrix} 1&1&\dots&&&\color{red}1&2\\ \vdots&\vdots&&&\!\!\!\color{red}{ {_{\displaystyle \raise -3pt\cdot}\displaystyle\cdot \,^{\displaystyle \cdot}}}&\color{red}2&3\\ \vdots&\vdots&&& \!\!\! \color{red}{ {_{\displaystyle \raise -3pt \cdot}\displaystyle\cdot\, ^{\displaystyle \cdot}}} &\color{red} \vdots& \vdots \\ 1&1&\dots &&&\color{red}{n-1} &n\\ 1&1&\dots &&\!\!\!\!\color{red}{n-1} &n&n\\ \vdots&\color{red}{ {_{\displaystyle\raise -3pt \cdot}\displaystyle\cdot \,^{\displaystyle \cdot}}}&\color{red}{ {_{\displaystyle \raise -3pt\cdot}\displaystyle\cdot \,^{\displaystyle \cdot}}}&&& \vdots & \vdots \\ \color{red}1&\color{red}2&\dots&&&n & n \\ 2&3&\dots&&&n & n \\ \end{pmatrix}$$ with constant antidiagonals, which has $\displaystyle \sum_{i=1}^{n-1}(n^2-i)=n^3-n-\frac{n(n-1)}2=O(n^3)$ turning points (in red). Or am I missing something?
(BTW is there a Latex command for rising \ddots?)