I'm suspicious that this problem is of the order O(2**N).

I suspect it is more like O(N!).

I also suspect that whilst inspecting the longest possible combinations for monotonicity, then in order of decreasing length so that you can short-circuit the full search space, sounds like an optimisation; in reality it will end up inspecting many more possibilities than a brute-force forward search with short-circuiting of the inner iterations.

I believe this can be reduced to LCS which is O(much better). Diff'ing the original data with its ordered copy would yield a sequence that (1) belongs to the original sequence, (2) is ordered and (3) is among the longest such sequences. (Answered below with code example).

I believe this can be reduced to LCS which is O(much better).

I concur. My assessment was of the OPs somewhat naive approach to the problem, not the optimal solution.

reduced to LCS

Careful. LCS can mean either: longest common substring; or -- as is applicable here -- longest common subsequence.

And actually, the OPs problem can be further specialised to Longest increasing subsequence, and tackled with a very straight forward algorithm that is O(n log n).

---

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority". I knew I was on the right track :)

In the absence of evidence, opinion is indistinguishable from prejudice.