Leetcode 2826. Sorting Three Groups

Given an array of values in {1,2,3}, remove the fewest elements so the remaining sequence is non-decreasing. This is equivalent to maximizing the length of a non-decreasing subsequence (or a subsequence of the form 1*2*3*), which can be solved with a small-state DP in O(n) time.