1912号:連合


import sys
input = sys.stdin.readline

n = int(input())
li = list(map(int,input().split()))
dp = li

for i in range(1,n):
    dp[i] = max(dp[i], dp[i-1] + li[i])

print(max(dp))
n個の数字をlist liに保存し、liと同じlist dpを作成します.
dpは連続するいくつかの数を含み、得られる和の中で最大の和を含む.
n=1の場合、dp[0]が出力されるので、範囲は1から始まる.
dp[i−1]が負の場合、dp[i]から新しい連続数が開始されるので、dp[i];
dp[i-1]が正の値の場合、li[i]に加算されるdp[i-1]+li[i]
次に、より大きな値の1つをdp[i]に位置決めする.
このようにして、すべてのリストdpを記入しmax(dp)を出力する.