<h1 id="heading">题目</h1>
<blockquote>
<h2 id="description">Description</h2>
<blockquote>
Redraiment是个聪明人，总是以奇怪的思考方法思考问题，但不知道为什么，他的解答总是最最巧妙，我们隆重地称他为诡异人！ 
有一天Jesse不经意中发现，诡异人的走路方法很特别，于是特别关注了他的走路规则。他发现诡异人总是往高处走，但走的步数总是最多，不知道为什么？你能替Jesse研究研究他最多走的步数吗？ 
发现了你也会是个聪明人!^_^
 
</blockquote>
<h2 id="input">Input</h2>
<blockquote>
There has several test cases. Each case start with an integer n(0 &lt; n ≤10000), then follows n integers hi, each seperated by a space. 1 ≤ hi ≤ 100),which represents the height of the place.
</blockquote>
<h2 id="output">Output</h2>
<blockquote>
For each case output a line with the max number of the steps he can go .
</blockquote>
<h2 id="sample-input">Sample Input</h2>
<blockquote>
5 
1 2 3 4 5 
6 
2 5 1 5 4 5
</blockquote>
<h2 id="sample-output">Sample Output</h2>
<blockquote>
5 
3
</blockquote>
<h2 id="hint">Hint</h2>
<blockquote>
6个点的高度各为 2 5 1 5 4 5 
如从第1格开始走,最多为3步, 2 4 5 
从第2格开始走,最多只有1步,5 
而从第3格开始走最多有3步,1 4 5 
从第5格开始走最多有2步,4 5
</blockquote>
</blockquote>
<h1 id="heading-1">题解</h1>
模板题 
<a href="/post/Algorithm/LIS.html">&gt;最长上升子序列&lt;</a>
<h1 id="heading-2">代码</h1>
<pre style="background-color:#fff">/*
By:OhYee
Github:OhYee
HomePage:http://www.oyohyee.com
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/

#include &lt;cstdio&gt;
#include &lt;algorithm&gt;
#include &lt;cstring&gt;
#include &lt;cmath&gt;
#include &lt;string&gt;
#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;list&gt;
#include &lt;queue&gt;
#include &lt;stack&gt;
#include &lt;map&gt;
#include &lt;set&gt;
using namespace std;

const int maxn = 10005;

int dp[maxn];
int a[maxn];

bool Do() {
 int n;
 if(scanf(&#34;%d&#34;,&amp;n) == EOF)
 return false;

 for(int i = 1;i &lt;= n;i++)
 scanf(&#34;%d&#34;,&amp;a[i]);

 memset(dp,0,sizeof(dp));

 int Max = 0;
 for(int i = 1;i &lt;= n;i++) {
 for(int j = 0;j &lt; i;j++)
 if(a[j] &lt; a[i] || j == 0)
 dp[i] = max(dp[i],dp[j] + 1);
 Max = max(Max,dp[i]);
 }

 printf(&#34;%d\n&#34;,Max);

 return true;
}

int main() {
 while(Do());
 return 0;
}
</pre>

AOJ 153.Redraiment的走法