[アルゴリズム]動的計画(Dynamic Programming)-白準1912回連続使用

import sys
input = sys.stdin.readline

n = int(input().rstrip())
numArr = list(map(int, input().rstrip().split(' ')))

for i in range(1, len(numArr)):
    numArr[i] = max(numArr[i], numArr[i-1]+numArr[i])

print(max(numArr))

解法

連続和は動的計画法における最も基本的な問題である.
前から配列で受け取った値を比較し、iの1番目の値と前の和を比較し、より大きな値を入れます.

誤った解釈

import sys
input = sys.stdin.readline

n = int(input().rstrip())
numArr = list(map(int, input().rstrip().split(' ')))

dp = []

for i in range(n):
    sub = [numArr[i]]
    for j in range(i+1, n):
        sub.append(sub[-1] + numArr[j])
    sub.sort()
    dp.append(sub[-1])

print(max(dp))   

動的プランニング法の方法が考えられなかった場合,加算したすべての値を比較した.
もちろんタイムアウト!
動的計画法をよりよく応用する方法を学ぶべきだと思います:)