Greatest three-digit number from a digit subsequence

You are given a list digits of single digits (each 0–9). Choose at most three of them, keep them in their original order, and read them left to right as a number. Return the largest number you can make.

Leading zeros are allowed: picking 0, 0, 4 gives 4.

Implement:

def greatest_triple(digits: list[int]) -> int: ...

Constraints

• 3 <= len(digits) <= 50
• 0 <= digits[i] <= 9

Example 1

digits = [2, 8, 1, 7, 3, 6]
output = 876

8 (index 1), 7 (index 3), 6 (index 5). No pick can start with a larger digit, and after the 8 the best two in order are 7 and 6.

Example 2

digits = [4, 6, 9]
output = 469

The 9 is last, so it cannot be the first digit of a three-digit pick, and any shorter pick is smaller.

Be ready to explain why choosing fewer than three digits never helps, and how your method changes if you must pick exactly k digits.

Clarifying questions

• Is the answer returned as an integer, so leading zeros vanish (004 is 4)?
• Can the list contain only zeros (answer 0)?
• For the follow-up with k digits, how large can k and the list get?

What a strong answer covers

• Picks greedily: the first digit is the largest among positions that still leave two digits after it, taking its leftmost occurrence; then the same for the second and third digits.
• Explains why fewer than three digits never helps: appending any digit, even 0, never makes the number smaller, since 10x + d >= x.
• Runs in O(n) for three digits (or brute force over all triples, O(n^3) = 125,000 at n = 50, which is fine to mention).
• Generalises to k digits with a monotonic stack: pop smaller digits while enough digits remain, O(n).
• Tests the examples, all zeros, a strictly increasing list, and a list where the maximum appears twice.

Follow-ups

• Pick exactly k digits.
• Pick from two lists while keeping each list's order (the 'create maximum number' problem).
• Return the indices of the chosen digits.