Trivial thought. It's bounded below by len(sequence) - count(shifts) - 2. There are local optimisations for both ends and for local alternations, but I don't think you ever need to consider a subsequence of length < 3 or 4. But I am rushing through on my way somewhere and will look later and prove it. Now am thinking that local optimisations give len(sequence) - (count(shifts) / 2) - 2 but have not proven that yet.