【部分列】FINAL問題【部分列】最長減少部分列 (paizaランク B 相当) 解答例 – PHP編【DPメニュー】

【DPメニュー】 > 【部分列】FINAL問題【部分列】最長減少部分列 (paizaランク B 相当)
※リンク先へ移動する為には「paiza」へのログインが必要です。

解答例

<?php
    $n = trim(fgets(STDIN));
    
    for($i = 0;$i < $n;$i++){
        $a[$i] = trim(fgets(STDIN));
    }
    
    for($i = 1;$i <= $n;$i++){
        for($j = 0;$j < $i;$j++){
            if($a[$j] > $a[$i]){
                $dp[$i] = max($dp[$i], $dp[$j] + 1);
            }
        }    
    }
 
    print(max($dp));
?>

<?php

$n = trim(fgets(STDIN));

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

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

}

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

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

if($a[$j] > $a[$i]){

$dp[$i] = max($dp[$i], $dp[$j] + 1);

}

print(max($dp));

カテゴリー:paiza - レベルアップ問題集

タグ:DPメニュー PHP paiza 問題集解答解答例

エッグ

解答例

シェアする

関連投稿

【PHP】アクセス修飾子について

【PHP】配列のポインタを操作する関数「current()」「next()」「prev()」「reset()」「end()」

【行によって長さが違う二次元配列の表示】STEP: 1 N 個の文字を半分ずつ出力 (paizaランク D 相当) – PHP編【標準出力メニュー】

【配列への副作用を伴う操作】STEP: 1 配列の順序の反転 (paizaランク D 相当) – PHP編【配列活用メニュー】

【行によって長さが違う二次元配列の表示】STEP: 3 直角三角形の出力 (paizaランク D 相当) – PHP編【標準出力メニュー】

【積の最小化】STEP: 6 池の周回 (paizaランク C 相当) 解答例 – PHP編【条件分岐メニュー】