YES

   1: max(x1,0()) -> x1
   2: max(s(x1),s(x2)) -> s(max(x2,x1))
   3: max(x1,x2) -> max(x2,x1)

@Jouannaud and Kirchner's criterion
--- R
   1: max(x1,0()) -> x1
   2: max(s(x1),s(x2)) -> s(max(x2,x1))
   3: max(x1,x2) -> max(x2,x1)

--- S
   1: max(x1,0()) -> x1
   2: max(s(x1),s(x2)) -> s(max(x2,x1))
   3: max(x1,x2) -> max(x2,x1)