🔢 背の順区間アルゴリズム - 詳細解析

📋 アルゴリズム概要

このアルゴリズムは動的プログラミング（DP）を使用して、連続する身長の非減少区間の最大長を効率的に求めます。

入力読み取り

人数nと各人の身長を配列に格納

DP初期化

dp[1] = 1として開始

DP計算

各位置で前の人との比較を実行

最大値取得

dp配列から最大値を返す

💻 実装コード

const fs = require('fs');

/**
 * 標準入力から文字列を読み取り、背の順区間の最長長さを計算する
 * @param {string} input - 標準入力の文字列
 * @returns {number} 背の順であるような区間のうち、最長であるものの長さ
 */
function findLongestNonDecreasingSequence(input) {
    const lines = input.trim().split('\n');
    const n = parseInt(lines[0]);
    
    // 身長データを配列に格納（1-indexedで扱うため先頭に0を追加）
    const heights = [0]; // heights[0]は使用しない
    for (let i = 1; i <= n; i++) {
        heights.push(parseInt(lines[i]));
    }
    
    // dp[i] = 人iが右端となる背の順区間の最長長さ
    const dp = new Array(n + 1);
    dp[1] = 1; // 最初の人は長さ1の区間
    
    // 動的プログラミングでdp配列を計算
    for (let i = 2; i <= n; i++) {
        if (heights[i - 1] <= heights[i]) {
            // 前の人の身長以上なら、前の区間に追加できる
            dp[i] = dp[i - 1] + 1;
        } else {
            // 前の人より身長が低いなら、新しい区間の開始
            dp[i] = 1;
        }
    }
    
    // dp配列の最大値を求める
    return Math.max(...dp.slice(1));
}

/**
 * メイン処理関数
 * 標準入力を読み取り、結果を標準出力に出力する
 */
function main() {
    try {
        // 標準入力を同期的に読み取り
        const input = fs.readFileSync('/dev/stdin', 'utf8');
        
        // 最長の背の順区間の長さを計算
        const result = findLongestNonDecreasingSequence(input);
        
        // 結果を出力
        console.log(result);
        
    } catch (error) {
        console.error('Error reading input:', error);
        process.exit(1);
    }
}

// メイン処理を実行
main();

🔍 具体例での動作解析

入力例: n=5, 身長=[160, 178, 170, 190, 190]

ステップバイステップ実行

初期状態
160
178
170
190
190
1
?
?
?
?

初期化: dp[1] = 1（最初の人は長さ1の区間）

⚙️ 各処理ステップの詳細

ステップ 1: i=2 (178)

比較: 160 ≤ 178 ✓

処理: dp[2] = dp[1] + 1 = 2

意味: 区間[1,2]が背の順（長さ2）

ステップ 2: i=3 (170)

比較: 178 > 170 ✗

処理: dp[3] = 1

意味: 新しい区間開始（長さ1）

ステップ 3: i=4 (190)

比較: 170 ≤ 190 ✓

処理: dp[4] = dp[3] + 1 = 2

意味: 区間[3,4]が背の順（長さ2）

ステップ 4: i=5 (190)

比較: 190 ≤ 190 ✓

処理: dp[5] = dp[4] + 1 = 3

意味: 区間[3,5]が背の順（長さ3）

📊 計算量解析

🕒 時間計算量: O(n)

各人について一度だけ処理を行うため、線形時間で解決できます。

  • 入力読み取り: O(n)
  • DP配列計算: O(n)
  • 最大値取得: O(n)
  • 合計: O(n)

💾 空間計算量: O(n)

身長配列とDP配列の2つのn要素配列を使用します。

  • heights配列: O(n)
  • dp配列: O(n)
  • 合計: O(n)

🔄 動的プログラミングの状態遷移

状態定義: dp[i] = 人iが右端となる背の順区間の最長長さ 
// 状態遷移式
if (heights[i-1] <= heights[i]) {
    dp[i] = dp[i-1] + 1;  // 前の区間を延長
} else {
    dp[i] = 1;            // 新しい区間を開始
}
🧠 アルゴリズムの核心

このアルゴリズムの美しさは、各位置で局所的な判断を行うことで、全体の最適解を求められる点にあります。

前の人より身長が高いか同じなら区間を延長し、低いなら新しい区間を開始する単純な規則で、すべての可能な背の順区間を効率的に探索できます。