【DPメニュー】【連続列】最長減少連続部分列 (paizaランク B)-解答例-PHP編

2022年8月15日

【DPメニュー】> FINAL問題【連続列】最長減少連続部分列 (paizaランク B 相当) [難易度: 1555 ±18]

※リンク先へ移動するためには[paiza]へのログインが必要です。

問題文

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 とします。

逆背の順であるような区間のうち、最長であるものの長さを出力してください。

入力値（例）
5
187
192
115
108
109

出力値（例）
3

解答例

<?php
    $n = trim(fgets(STDIN));
    
    $a = array();
    
    for ($i = 0; $i < $n; $i++) {
        $a[] = trim(fgets(STDIN));
    }
    
    $dp = array();
    $dp[0] = 1;
    
    for ($i = 1; $i < $n; $i++) {
        
        if ($a[$i-1] >= $a[$i]) {
            $dp[$i] = $dp[$i-1] + 1;
            
        } else {
            $dp[$i] = 1;
        }
    }
    
    echo max($dp);
?>

<?php

$n = trim(fgets(STDIN));

$a = array();

for ($i = 0; $i < $n; $i++) {

$a[] = trim(fgets(STDIN));

}

$dp = array();

$dp[0] = 1;

for ($i = 1; $i < $n; $i++) {

if ($a[$i-1] >= $a[$i]) {

$dp[$i] = $dp[$i-1] + 1;

} else {

$dp[$i] = 1;

}

echo max($dp);

解答例

カテゴリー