[백준] 연속합

출처:: www.acmicpc.net/problem/1912

분류:: dp

 

1. 문제 이해 및 해결과정

- 10, -4, 3, 1, 5, 6, -35, 12, 21, -1  1) 10까지, 10 2) -4까지, 6 (10, 10-4) 3) 3까지, 10-4+3, -4+3, 3 = 9, -1, 3  4) 1까지,10-4+3+1, -4+3+1, 3+1, 1 = 10,0,4,1 => dp[i]=max(dp[i],dp[i-1]+arr[i]) dp= [10, 6, 9, 10, 15, 21, 0, 12, 33, 32]

 

2. 풀이방법

  1. [python] dp

#연속합
#https://www.acmicpc.net/problem/1912
import sys
sys.stdin = open("input.txt","r")
input=sys.stdin.readline
n=int(input())
arr=list(map(int,input().split()))
dp=arr #i를 마지막항으로 했을 때 연속된 합이 가장 큰 수

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

# print(dp)
print(max(dp))

 

3. 오답원인

  1. 입력받은 수가 음수일때를 고려하지 않고, dp를 0으로 초기화 하였다

#연속합
#https://www.acmicpc.net/problem/1912
import sys
input=sys.stdin.readline
n=int(input())
arr=list(map(int,input().split()))
dp=[0]*(n) #i를 마지막항으로 했을 때 연속된 합이 가장 큰 수
dp[0]=arr[0]
for i in range(1,n):
    for j in range(i):
        dp[i]=max(dp[i],dp[i-1]+arr[i])

print(max(dp))

 

4. 알게된 점