[白俊-1398]連続2

コード#コード#

import sys
input = sys.stdin.readline

n=int(input())
a=list(map(int,input().split()))

dp=[[0]*n for _ in range(2)]
dp[0][0]=a[0]

if n>1:
    result=-sys.maxsize
    for i in range(1,n):
        dp[0][i]=max(dp[0][i-1]+a[i],a[i])
        dp[1][i]=max(dp[1][i-1]+a[i],dp[0][i-1])
        result=max(result,dp[0][i],dp[1][i])
    print(dp)
    print(result)
else:
    print(dp[0][0])

実行時間:208ミリ秒

に答える

考えてみたが解けず、検索で解けた.
dp[0][i]一部の要素は削除されません.
dp[1][i]はいくつかの要素を削除した.
要素(前の連続+i要素)と(i要素)を削除しない場合は、大きな値を入力します.
一部の要素を削除する場合は、2つに分けられます.
1.最初の要素が削除されました
2.i以前の要素を削除した場合
1番はdp[0][i-1]です.
2号はdp[1][i-1]+a[i].
1番と2番に大金を代入する.
繰り返し終了後に最大値を出力します.
print(max(dp[0])、max(dp[1])で最大値を探し、要素が負の数であればdp[1][0]と同じ0を最大値としてエラー答えを探します.
また、n=1の場合、1つのオープンソースサイトを選択しなければならないので、1つのオープンソースサイトを出力する.