白準連続合(1912)
Dynamic Programming
質問する
n個の整数からなる任意の数列を与える.私たちはその中からいくつかの連続する数を選択して、求めた和の中で最大の和を求めたいです.ただし、数量は1つ以上を選択する必要があります.
例えば、10,−4,3,1,5,6,−35,12,21,−1である.ここで正解は12+21人33が正解
入力
第1行は整数n(1≦n≦100000)を与え、第2行はn個の整数からなる数列を与える.数が-1000以上、または1000未満の整数です.
しゅつりょく
最初の行に答えを印刷します.
タイムアウトコード
import sys
input = sys.stdin.readline
n = int(input())
li = []
answer = []
li = list(map(int, input().split()))
dp = [0] * n
for i in range(n):
if i != n - 1:
plus = li[i]
maxi = li[i]
for j in range(i + 1, n):
plus += li[j]
if(plus >= maxi):
maxi = plus
dp[i] = maxi
else:
dp[i] = li[i]
print(max(dp))
import sys
input = sys.stdin.readline
n = int(input())
numList = list(map(int, input().split()))
temp = [0] * n
result = -1000
for i in range(n):
temp[i] = max(temp[i - 1]+ numList[i], numList[i])
result = max(result, temp[i])
print(result)Reference
この問題について(白準連続合(1912)), 我々は、より多くの情報をここで見つけました https://velog.io/@skkfea07/백준-연속합1912テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol