BAEKJOON : 1912

Codren·2021년 7월 18일
0

No. 11053

1. Problem




2. My Solution

  • dp[i] 값을 i 번째 수열의 요소까지 살펴보았을 때 가장 큰 연속합으로 설정
  • i-1 번째 수열의 요소까지 살펴보았을 때의 최대값에 자기 자신을 더한값과 자기 자신의 값중에 큰 값을 dp값으로 설정
  • dp[i] = max(seqeunce[i],dp[i-1]+seqeunce[i])
import sys

n = int(sys.stdin.readline().rstrip()) 
seqeunce = list(map(int,sys.stdin.readline().rstrip().split()))   
dp = [0] * n

for i in range(n):
    if i == 0:
        dp[i] = seqeunce[i]
    else:
        dp[i] = max(seqeunce[i],dp[i-1]+seqeunce[i]) 

print(max(dp))




3. Learned

  • dp 리스트의 값을 n = 1,2,3...n 일때의 값으로 할것인지, 아니면 해당 요소를 포함했을 경우의 값으로 할 것인지 설정해야함 (전자 - 피보나치 ../ 후자 - 수열 ..)

0개의 댓글