⚡ パフォーマンス比較解析：最適化DPアルゴリズム

🏆 パフォーマンス比較結果

🔍 コード比較分析

📋 高速版コード

from typing import List

class Solution:
    def longest_non_increasing_segment(self, n: int, a: List[int]) -> int:
        """
        DP を用いて最長の「逆背の順」区間の長さを求める
        Parameters
        ----------
        n : int
            人数 (1 <= n <= 200,000)
        a : List[int]
            各人の身長リスト (100 <= a_i <= 200)
        Returns
        -------
        int
            最長の「逆背の順」区間の長さ
        """
        # dp[i]: i番目で終わる逆背の順の長さ
        dp: List[int] = [1] * n
        max_len: int = 1
        
        for i in range(1, n):
            if a[i-1] >= a[i]:
                dp[i] = dp[i-1] + 1
            else:
                dp[i] = 1
            if dp[i] > max_len:
                max_len = dp[i]
        
        return max_len

if __name__ == "__main__":
    import sys
    input_data = sys.stdin.read().strip().split()
    n: int = int(input_data[0])
    a: List[int] = list(map(int, input_data[1:]))
    
    solver = Solution()
    result: int = solver.longest_non_increasing_segment(n, a)
    print(result)

📋 従来版コード

def find_longest_decreasing_interval_dp_optimized(n: int, heights: list[int]) -> int:
    if n == 0:
        return 0
    if n == 1:
        return 1
    
    max_length: int = 1  # 全体での最大長
    current_dp: int = 1  # dp[i]に相当（現在位置での最長区間長）
    
    for i in range(1, n):
        if heights[i-1] >= heights[i]:  # 非増加条件を満たす場合
            current_dp += 1  # 前の区間を延長
        else:
            current_dp = 1  # 新しい区間開始
        
        max_length = max(max_length, current_dp)
    
    return max_length

def main() -> None:
    n: int = int(input().strip())
    heights: list[int] = []
    
    for _ in range(n):
        height: int = int(input().strip())
        heights.append(height)
    
    result: int = find_longest_decreasing_interval_dp_optimized(n, heights)
    print(result)

🚀 パフォーマンス向上の要因分析

📊 ベンチマーク結果の視覚化

🔬 詳細パフォーマンス分析

💾 メモリアクセスパターンの違い

# 高速版：連続メモリアクセス（キャッシュ効率◎）
dp: List[int] = [1] * n  # 一括確保
for i in range(1, n):
    dp[i] = dp[i-1] + 1 if a[i-1] >= a[i] else 1  # 順次アクセス

# 従来版：スカラー変数（メモリ効率は良いが、キャッシュ予測困難）
current_dp: int = 1  # 単一変数
for i in range(1, n):
    current_dp = current_dp + 1 if heights[i-1] >= heights[i] else 1

⚡ 入出力処理の違い

# 高速版：一括入力処理（1回のシステムコール）
input_data = sys.stdin.read().strip().split()
n: int = int(input_data[0])
a: List[int] = list(map(int, input_data[1:]))

# 従来版：個別入力処理（n+1回のシステムコール）
n: int = int(input().strip())
heights: list[int] = []
for _ in range(n):
    height: int = int(input().strip())
    heights.append(height)

🎯 最適化のトレードオフ