[アルゴリズム/標準]13398:連続2(python)
既存の連続と一つ抜きの連続を比較すればよい.
dp[0][i]を削除せずに求める連続
dp[1][i]は削除して求める連続である
dp[1][i] = max(dp[0][i-1], dp[1][i-1] + a[i])
「現在の数値の削除」および「既存の数値の削除」から、大きな数を選択します.
N = int(input())
a = list(map(int, input().split()))
dp = [[0] * N for _ in range(2)]
dp[0][0] = a[0]
dp[1][0] = -1000
for i in range(1, N):
dp[0][i] = max(dp[0][i - 1] + a[i], a[i])
dp[1][i] = max(dp[0][i - 1], dp[1][i - 1] + a[i])
print(max(max(dp[0]), max(dp[1])))Reference
この問題について([アルゴリズム/標準]13398:連続2(python)), 我々は、より多くの情報をここで見つけました https://velog.io/@y7y1h13/알고리즘백준-13398-연속합-2pythonテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol