最長増加連続部分列 Scala編（paizaランク B 相当）

n 人が横一列に並んでいます。左から i 番目の人を人 i と呼ぶことにします。人 i の身長は a_i [cm]です。
人 l ,人 l+1, ... , 人 r からなる区間 [l, r] について、すべての l ≦ i < r に対して a_i ≦ a_{i+1} が成り立っているとき、区間 [l, r] は背の順であると呼ぶことにします。また、区間 [l, r] の長さを r-l+1 とします。
背の順であるような区間のうち、最長であるものの長さを出力してください。

---

(ヒント)

元の問題を解くために、部分問題としてどのような問題を考えればよいでしょうか。

dp[n] を、人 n が右端となっているような背の順区間のうち、最長であるような区間の長さとしてみましょう。dp[1] ~ dp[k-1] が既に求まっているとして、dp[k] がどうなるかを考えてみましょう。dp[k-1] に注目すると、dp[k-1] は人 k-1 を右端とする背の順区間の長さですから、もし a_{k-1} ≦ a_k なら、その区間の右端に人 k をくっつけることで新しく長さ dp[k-1]+1 の背の順区間を作ることができ、この区間の長さは人 k を右端として持つ背の順区間のうち最長であることがわかります。逆に、もし a_{k-1} ＞ a_k なら、人 k が右端となるような背の順区間は人 k のみからなる長さ1の区間しか存在しないことがわかります。

以上の考察により、dp[k-1] と dp[k] の関係が明らかになりました。自信のある人は自分で漸化式を立ててみましょう。以下の疑似コードに従って、自分の得意な言語で実装してみましょう。

dp[1] <- 1

for i = 2 to n
    if a[i-1] <= a[i] then
        dp[i] <- dp[i-1]+1
    else
        dp[i] <- 1

print max({dp[1], ... ,dp[n]})