問題一覧 > 通常問題

No.127 門松もどき

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 51
作問者 : krotonkroton
6 ProblemId : 293 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2016-05-24 14:38:07

問題文

竹林とは、竹の長さを表す正の整数列 A1,A2AN のことである。
門松もどきとは、1i1<i2<<iMN を満たす竹林の部分列 Ai1,Ai2AiM
Ai1<AiM<Ai2<AiM1<Ai3 もしくは AiM<Ai1<AiM1<Ai2<AiM2 を満たすものをいう。

最長の門松もどきの長さを答えよ。

例: 長さ6の門松もどき

入力

N
A1 A2  AN

入力はすべて整数で与えられる。

  • 1N3000
  • 1Ai100000

出力

最長の門松もどきの長さを出力してください。

サンプル

サンプル1
入力
6
1 4 7 10 6 2
出力
6
サンプル2
入力
7
1 4 7 3 10 6 2
出力
6

門松もどきは「部分列」であることに注意してください

サンプル3
入力
10
5 9 5 11 20 5 12 17 6 18
出力
5
サンプル4
入力
2
5 5
出力
1

1本でも門松もどきなのだ

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。