[アルゴリズム/標準]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])))