[BOJ/Python]数列2491

5884 ワード
dynamic programming DP python boj テキストリンク

この問題はダイナミックプログラミングによって解決された.以前の値と比較して、dpを更新し、その最大値を見つけて出力します.最初は問題を正しく読んでいなかったので、前<=後、前>=後の場合はすべてdpを表すのではなく、前<=後のdpのみを表すので、誤って処理された.この問題についての点火式は以下の通りである.dp[n]=max(dp[n], dp[n-1]+1)<=の場合も>=の場合も解く必要があるため、dp配列を2次元と宣言し、dp[i][0]が<=を格納する場合、dp[i][1]が>=を格納する場合.
  • nと入力します.
  • arrと入力します.
  • dp配列を2次元として宣言し、1はn個を充填する.
  • 1からn−1まで繰り返されるiに対してfor文を行う.
    ->arr[i]がarr[i-1]以上である場合、dp[0][i]はdp[0][i]およびdp[0][i-1]+1のより大きな値に更新される.
    ->arr[i]がarr[i-1]以下である場合、dp[1][i]はdp[1][i]およびdp[1][i-1]+1のより大きな値に更新される.
    • 出力
  • dp[0]の最大値とdp[1]の最大値より大きい値を出力します.

    • Code

    n=int(input())
arr=list(map(int, input().split()))
dp=[[1]*n for _ in range(2)]
for i in range(1,n):
    if arr[i]>=arr[i-1]:
        dp[0][i]=max(dp[0][i], dp[0][i-1]+1)
    if arr[i]<=arr[i-1]:
        dp[1][i]=max(dp[1][i], dp[1][i-1]+1)
print(max(max(dp[0]), max(dp[1])))
    Thisと矢印関数
    学習反応(1)-機能設定状態()