YES

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

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

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


NOTE: input TRS is reduced

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

reduced to
   2: max(0(),x2) -> x2
   3: max(s(x1),s(x2)) -> s(max(x2,x1))
   4: max(x1,x2) -> max(x2,x1)