Given a positive integer of n digits, such as 1214532 (n = 7), delete k digits (for example, k = 4) so that the resulting integer is the smallest.
A greedy algorithm for this would still eliminate digits, so that the resulting integer is the smallest. For the previous example:
Step 1: Delete 2 => 114532 Step 2: Delete 5 => 11432 Step 3: Delete 4 => 1132 Step 4: Delete 3 => 112
Can you prove that this algorithm is optimal (that is, the final integer is the smallest possible)? Or if it is not, show a counterexample?