The construction of simple classification rules is a frequent problem in medical research. Maximally selected rank statistics allow the evaluation of cutpoints, which provide the classification of observations into two groups by a continuous or ordinal predictor variable. The computation of the exact distribution of a maximally selected rank statistic is discussed and a new lower bound of the distribution is derived based on an extension of an algorithm for the exact distribution of a linear rank statistic. Therefore, the test based on the upper bound of the P-value is of level α. For small to moderate sample sizes the lower bound of the exact distribution is a substantial improvement compared to approximations based on an improved Bonferroni inequality or based on the asymptotic Gaussian process. The lower bound of the distribution is compared to the exact distribution by means of a simulation study and the proposal is illustrated by three clinical studies.