Your solution is calling max(@xs) twice each step. This leads to O(2^n) growth for what should be an O(n) problem. Modifying it slightly to call max once and save the value in a temp variable should save considerable time on long lists.

sub max {
    my ($x, @xs) = @_;
    @xs ? do { my $m = maxdo(@xs); ($x, $m)[$x < $m] } : $x;
}
[download]