Forcing a monotone subsequence
What is the smallest such that every sequence of distinct real numbers is guaranteed to contain a subsequence of length (not necessarily consecutive) that is either strictly increasing or strictly decreasing?
Show hints (3)+
- Attach to each term the longest increasing and decreasing subsequences ending there.
- Why must two different terms get different label pairs?
- Build a 16-term example out of decreasing blocks.
Answer
Reveal answer →Final answer
17
Create a free account to see the full worked solution and track your progress.
Interview format: Trading Aptitude Tests, Systematic & Data-Driven Trading