Example 3 Suppose point $P$ starts from lattice point $A(1,1)$ and moves to point $B(m, n)\left(m, n \in \mathbf{N}^{*}\right)$ along the grid with the shortest path, i.e., each time it moves to another lattice point, the x-coordinate or y-coordinate increases by 1. Find the maximum value of the sum $S$ of the products of the coordinates of all lattice points that point $P$ passes through.

---

The translation preserves the original text's line breaks and formatting.
Let the points passed by $P$ be $P_{1}=A(1,1), P_{2}, \cdots, P_{m+n-1}=B(m, n)$, and the coordinates of $P_{i}$ be $\left(x_{i}, y_{i}\right)$, then $S=\sum_{i=1}^{m+n-1} x_{i} y_{i}$. To maximize $S$, intuitively, $x_{i}$ and $y_{i}$ should be as close as possible. However, it is not required that for any $i$, $x_{i}=y_{i}$ (otherwise, it would move along the diagonal). We conjecture that if $\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{m+n-1}, y_{m+n-1}\right)$ maximize $S$, then for any $x_{i}1\left(x_{i}1$. At this point, the natural idea is: decrease $x_{i}$ by 1 and increase $y_{i}$ by 1. That is, adjust the point $P_{i}\left(x_{i}, y_{i}\right)$ to $P_{i}^{\prime}\left(x_{i}-1, y_{i}+1\right)$, keeping the other points unchanged. But does the adjusted path still meet the conditions? Clearly, to ensure the adjusted path still meets the conditions, $P_{i}$ should satisfy: $P_{i-1} P_{i}$ is a horizontal edge and $P_{i} P_{i+1}$ is a vertical edge. However, $P_{i}$ may not satisfy such conditions. At this point, observe the path and find that there must be a point $P_{t}\left(x_{t}, y_{t}\right)$ that satisfies such conditions, i.e., there exist three consecutive points $P_{t-1}\left(x_{t-1}, y_{t-1}\right), P_{t}\left(x_{t}, y_{t}\right), P_{t+1}\left(x_{t+1}, y_{t+1}\right)$, such that $P_{t-1} P_{t}$ is a horizontal edge and $P_{t} P_{t+1}$ is a vertical edge, and $x_{t}-y_{t}>1$.

Actually, if $P_{i-1} P_{i}$ is a vertical edge, then consider the point with the smallest $y$-coordinate and the same $x$-coordinate as $x_{i}$. Let this point be $P_{t}\left(x_{t}, y_{t}\right)$, where $x_{t}=x_{i}, y_{t}x_{i}-y_{i}>1$. Since $x_{t}>1+y_{t}>1$, there must be a horizontal edge before reaching $P_{t}\left(x_{t}, y_{t}\right)$. Thus, by the minimality of $y_{t}$, $P_{t-1} P_{t}$ is a horizontal edge, and $P_{t} P_{t+1}$ is a vertical edge. If $P_{i-1} P_{i}$ is a horizontal edge, then consider the point with the largest $x$-coordinate and the same $y$-coordinate as $y_{i}$. Let this point be $P_{t}\left(x_{t}, y_{t}\right)$, where $x_{t}>x_{i}, y_{t}=y_{i}$. At this point, $x_{t}-y_{t}=x_{t}-y_{i}>x_{i}-y_{i}>1$. Since $y_{i}1$, there must exist such three consecutive points $P_{t-1}\left(x_{t-1}, y_{t-1}\right), P_{t}\left(x_{t}, y_{t}\right), P_{t+1}\left(x_{t+1}, y_{t+1}\right)$, such that $P_{t-1} P_{t}$ is a horizontal edge and $P_{t} P_{t+1}$ is a vertical edge, and $x_{t}-y_{t}>1$. Thus, replacing $P_{t}\left(x_{t}, y_{t}\right)$ with $P_{t}^{\prime}\left(x_{t}-1, y_{t}+1\right)$, the resulting path still meets the requirements. But $\left(x_{t}-1\right)\left(y_{t}+1\right)=x_{t} y_{t}+x_{t}-y_{t}-1>x_{t} y_{t}$. Therefore, the value of $S$ increases after the adjustment, leading to a contradiction.

From the above, for any point $P_{i}\left(x_{i}, y_{i}\right)$ on the path, if $x_{i} \neq y_{i}$, then the next point from $P_{i}\left(x_{i}, y_{i}\right)$ is unique, and the next point is the one that increases the smaller coordinate by 1. When $x_{i}=y_{i}$, there are two choices for the next point from $P_{i}\left(x_{i}, y_{i}\right)$, which is to increase either the $x$-coordinate or the $y$-coordinate by 1. Thus, when $m \geqslant n$, the path is:
$$
\begin{array}{l}
A(1,1) \rightarrow P_{2}(2,1) \text { or } P_{2}(1,2) \rightarrow P_{3}(2,2) \rightarrow P_{4}(2,3) \text { or } P_{4}(3,2) \rightarrow \\
P_{5}(3,3) \rightarrow \cdots \rightarrow P_{2 n-1}(n, n) \rightarrow P_{2 n}(n+1, n) \rightarrow P_{2 n+1}(n+2, n) \rightarrow \cdots \rightarrow \\
P_{m+n-1}(m, n) \text {. } \\
\text { At this point, } \\
S_{\text {max }}=\sum_{i=1}^{n} i^{2}+\sum_{i=1}^{n-1} i(i+1)+n \sum_{i=1}^{m-n}(n+i) \\
=\frac{1}{6} n\left(3 m^{2}+n^{2}+3 m-1\right) .
\end{array}
$$

When $m<n$, similarly, we get $S_{\text {max }}=\frac{1}{6} m\left(3 n^{2}+m^{2}+3 n-1\right)$.