1912

날짜 : 2022. 11. 18

사용 언어 : python

 

문제

 

 

코드

import sys

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

for i in range(1, n):
    # 현재 수열의 수와 합했을 때의 수와 비교(더했을 때 감소하는 경우 또한 저장)
    # 감소하는 경우는 max를 통해 자연스럽게 필터링
    dp.append(max(dp[i - 1] + a[i], a[i])) 
print(max(dp))
#print(dp)

 

 

풀이

- 해당 수에 대해서 일관적으로 더해 나감으로써 비교해 나가는 문제였다.

 

 

알게된 점

- 현재 수열의 수와 합했을 때의 수와 비교한다는 아이디어가 잘 떠오르지 않았던 것 같다.

 

 

참고 사이트

- https://pacific-ocean.tistory.com/96

백준 알고리즘 1912번(python 파이썬)