No.127 Pseudo-Kadomatsu
krotonProblem Statement
A bamboo grove is a sequence of positive integers \(A_{1}, A_{2} \ldots A_{N}\) representing the lengths of bamboo.
A pseudo-kadomatsu is a subsequence \(A_{i_{1}}, A_{i_{2}} \ldots A_{i_{M}}\) of the bamboo grove, with \(1 \leq i_{1} < i_{2} < \ldots < i_{M} \leq N\), that satisfies
\(A_{i_{1}} < A_{i_{M}} < A_{i_{2}} < A_{i_{M-1}} < A_{i_{3}} \ldots\) or \(A_{i_{M}} < A_{i_{1}} < A_{i_{M-1}} < A_{i_{2}} < A_{i_{M-2}} \ldots\).
Find the length of the longest pseudo-kadomatsu.
Example: a pseudo-kadomatsu of length 6
Input
\(N\)
\(A_{1}\) \(A_{2}\) \(\ldots\) \(A_{N}\)
All inputs are given as integers.
- \(1 \leq N \leq 3000\)
- \(1 \leq A_{i} \leq 100000\)
Output
Output the length of the longest pseudo-kadomatsu.
Sample
Sample 1
Input
6 1 4 7 10 6 2
Output
6
Sample 2
Input
7 1 4 7 3 10 6 2
Output
6
Note that a pseudo-kadomatsu is a "subsequence".
Sample 3
Input
10 5 9 5 11 20 5 12 17 6 18
Output
5
Sample 4
Input
2 5 5
Output
1
Even a single bamboo counts as a pseudo-kadomatsu.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。