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)を出力する.
Reference
この問題について(1912号:連合), 我々は、より多くの情報をここで見つけました https://velog.io/@mae03087/1912번-연속합テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol