YES

Problem:
 max(L(x)) -> x
 max(N(L(0()),L(y))) -> y
 max(N(L(s(x)),L(s(y)))) -> s(max(N(L(x),L(y))))
 max(N(L(x),N(y,z))) -> max(N(L(x),L(max(N(y,z)))))

Proof:
 DP Processor:
  DPs:
   max#(N(L(s(x)),L(s(y)))) -> max#(N(L(x),L(y)))
   max#(N(L(x),N(y,z))) -> max#(N(y,z))
   max#(N(L(x),N(y,z))) -> max#(N(L(x),L(max(N(y,z)))))
  TRS:
   max(L(x)) -> x
   max(N(L(0()),L(y))) -> y
   max(N(L(s(x)),L(s(y)))) -> s(max(N(L(x),L(y))))
   max(N(L(x),N(y,z))) -> max(N(L(x),L(max(N(y,z)))))
  Usable Rule Processor:
   DPs:
    max#(N(L(s(x)),L(s(y)))) -> max#(N(L(x),L(y)))
    max#(N(L(x),N(y,z))) -> max#(N(y,z))
    max#(N(L(x),N(y,z))) -> max#(N(L(x),L(max(N(y,z)))))
   TRS:
    max(N(L(0()),L(y))) -> y
    max(N(L(s(x)),L(s(y)))) -> s(max(N(L(x),L(y))))
    max(N(L(x),N(y,z))) -> max(N(L(x),L(max(N(y,z)))))
   Matrix Interpretation Processor: dim=1
    
    usable rules:
     max(N(L(0()),L(y))) -> y
     max(N(L(s(x)),L(s(y)))) -> s(max(N(L(x),L(y))))
     max(N(L(x),N(y,z))) -> max(N(L(x),L(max(N(y,z)))))
    interpretation:
     [max#](x0) = x0 + 2,
     
     [s](x0) = x0 + 3,
     
     [N](x0, x1) = x0 + 2x1 + 1,
     
     [0] = 1,
     
     [max](x0) = x0,
     
     [L](x0) = 1/2x0
    orientation:
     max#(N(L(s(x)),L(s(y)))) = 1/2x + y + 15/2 >= 1/2x + y + 3 = max#(N(L(x),L(y)))
     
     max#(N(L(x),N(y,z))) = 1/2x + 2y + 4z + 5 >= y + 2z + 3 = max#(N(y,z))
     
     max#(N(L(x),N(y,z))) = 1/2x + 2y + 4z + 5 >= 1/2x + y + 2z + 4 = max#(N(L(x),L(max(N(y,z)))))
     
     max(N(L(0()),L(y))) = y + 3/2 >= y = y
     
     max(N(L(s(x)),L(s(y)))) = 1/2x + y + 11/2 >= 1/2x + y + 4 = s(max(N(L(x),L(y))))
     
     max(N(L(x),N(y,z))) = 1/2x + 2y + 4z + 3 >= 1/2x + y + 2z + 2 = max(N(L(x),L(max(N(y,z)))))
    problem:
     DPs:
      
     TRS:
      max(N(L(0()),L(y))) -> y
      max(N(L(s(x)),L(s(y)))) -> s(max(N(L(x),L(y))))
      max(N(L(x),N(y,z))) -> max(N(L(x),L(max(N(y,z)))))
    Qed