Yahoo Answers is shutting down on May 4th, 2021 (Eastern Time) and the Yahoo Answers website is now in read-only mode. There will be no changes to other Yahoo properties or services, or your Yahoo account. You can find more information about the Yahoo Answers shutdown and how to download your data on this help page.
Trending News
How does Erdős–Szekeres theorem work?
I'm reading http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Sz...
Based on the description it seems that:
If r=3 and s=3, the sequence has to be at least (r − 1)(s − 1) + 1 = 5. Let's say my sequence is 1,2,3,4,5. But the permutation 1,5,2,4,3 has the longest increasing subsequence of only 2 and the longest decreasing subsequence of only 2, right?
What am I misunderstanding?
2 Answers
- Awms ALv 71 decade agoFavorite Answer
124 and 123 are both increasing subsequences of length 3, and 543 is a decreasing subsequence of length 3.
Subsequences need not be with consecutive numbers.
- ?Lv 71 decade ago
1,5,2,4,3 has an increasing subsequence 1,2,3 and another 1,2,4 both of length 3 = r = s. It also has a decreasing subsequence 5,4,3 of length 3.
