[백준] 1912번 연속합(python)(dp)

https://www.acmicpc.net/problem/1912

1912번: 연속합

 

1. 난이도 실버2 (🥈) 

 

2. 내가 작성한 코드

n = int(input())

dp = [0] * n

num = list(map(int, input().split()))

dp[0] = num[0]

for i in range(1,n):
  if dp[i-1] + num[i] > num[i]: 
    dp[i] = dp[i-1] + num[i]
  else:
    dp[i] = num[i]

print(max(dp))

 

dp에 누적합을 저장해준다. 이때, 누적합 + 본인의 값이 작아지면 소용이 없다.

 

따라서 '(본인의 앞까지의 누적합 + 본인의 값) > 본인의 값'의 경우에만

 

dp[본인의 값] = 본인의 앞까지의 누적합 + 본인의 값 으로 갱신해주면 된다.

 

 

3. 수정

n = int(input())

dp = [0] * n

num = list(map(int, input().split()))

dp[0] = num[0]

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

if문을 사용하여 검토할 필요없이 max 함수를 이용하면 된다.