Consider the TRS R consisting of the rewrite rules

1: max(L(x)) -> x
2: max(N(L(0),L(y))) -> y
3: max(N(L(s(x)),L(s(y)))) -> s(max(N(L(x),L(y))))
4: max(N(L(x),N(y,z))) -> max(N(L(x),L(max(N(y,z)))))

There are 3 dependency pairs:

5: MAX(N(L(s(x)),L(s(y)))) -> MAX(N(L(x),L(y)))
6: MAX(N(L(x),N(y,z))) -> MAX(N(L(x),L(max(N(y,z)))))
7: MAX(N(L(x),N(y,z))) -> MAX(N(y,z))

The approximated dependency graph contains 2 SCCs:
{5}
and {7}.

- Consider the SCC {5}.
There are no usable rules.
By taking the polynomial interpretation
[L](x) = [MAX](x) = [s](x) = x + 1
and [N](x,y) = x + y + 1,
rule 5
is strictly decreasing.

- Consider the SCC {7}.
There are no usable rules.
By taking the polynomial interpretation
[L](x) = [MAX](x) = x + 1
and [N](x,y) = x + y + 1,
rule 7
is strictly decreasing.

Hence the TRS is terminating.