【部分列】STEP: 1 最長部分増加列 (paizaランク B 相当) 解答例 – PHP編【DPメニュー】

解答例

<?php
    $n = trim(fgets(STDIN));
    $dp[1] = 1;
    $a[1] = trim(fgets(STDIN));
    for($i = 2;$i <= $n;$i++){
        $test = trim(fgets(STDIN));
        $a[$i] = $test;
        $dp[$i] = 1;  // 木 i のみからなる部分列の長さ
        for($j = 1;$j <= ($i - 1);$j++){
            if($a[$j] < $a[$i]){
                $dp[$i] = max($dp[$i], $dp[$j] + 1);    // 最後が木 j であるような増加部分列の末尾に木 i をくっつける  
            }
        }
    }
    echo max($dp);
?>

<?php

$n = trim(fgets(STDIN));

$dp[1] = 1;

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

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

$test = trim(fgets(STDIN));

$a[$i] = $test;

$dp[$i] = 1; // 木 i のみからなる部分列の長さ

for($j = 1;$j <= ($i - 1);$j++){

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

$dp[$i] = max($dp[$i], $dp[$j] + 1); // 最後が木 j であるような増加部分列の末尾に木 i をくっつける

}

echo max($dp);

paiza - レベルアップ問題集

エンジニアゲート

【部分列】STEP: 1 最長部分増加列 (paizaランク B 相当) 解答例 – PHP編【DPメニュー】

解答例

コメントを残すコメントをキャンセル

解答例

シェアする

関連投稿

【早解13】満員電車の乗車率(paizaランク D 相当) 解答例 – PHP編【Dランク早解きセット】

【特定の文字で区切り 1 行で出力】STEP: 3 カンマ区切りで 10 個出力 1 (paizaランク D 相当) – PHP編【標準出力メニュー】

【静的メンバ】STEP: 1 クラスの作成 (paizaランク C 相当) 解答例 – PHP編【クラス・構造体メニュー】

【PHP】XAMPPでドキュメントルートフォルダを設定・変更する方法

【PHP】繰り返し処理終了させたり、処理を中断させて次の処理を実行させる方法 「break」「continue」

【漸化式】STEP: 2 2項間漸化式 2 (paizaランク C 相当) 解答例 – PHP編【DPメニュー】

コメントを残す コメントをキャンセル

【PHP】繰り返し処理終了させたり、処理を中断させて次の処理を実行させる方法「break」「continue」

コメントを残すコメントをキャンセル