[python] 1912. 연속합

• 문제

---

 

 

 

• 올바른 풀이

n = int(input())
num_list = list(map(int, input().split()))

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

 

해당 문제는 다이나믹 프로그래밍으로 해결할 수 있다.

최댓값을 구하기 위한 풀이방법은 다음과 같다. 

i번째까지의 수를 더한 값보다 i번째 값이 크면 그 이전 값은 무시한다.

 

즉, i번째까지의 누적값이 i번째보다 작으면 계속해서 더해가지만

i번째 값이 크면 누적값을 무시하고 i번째부터 다시 값을 더해간다고 이해하면 될 것 같다.