[1912] 연속합 (Python)

1912번: 연속합

 

풀이

---

 

이 문제는 연속된 순열의 합 중 가장 큰 수를 구하는 것입니다.

 

해당 문제를 접근하기 위해 다음과 같이 가정했습니다.

 

1. 어떤 한 부분의 연속된 합을 구할 때 앞서 선행된 계산들이 완료되었다.

2. 해당 부분의 가장 긴 연속된 합은 (앞서 선행된 계산 + 현재의 값)과 (현재의 값)을 비교하여 더 큰 값이다.

 

이 조건들이 만족된다면 가장 큰 연속 합을 구할 수 있습니다.

 

정답 코드

---

# 다이나믹 프로그래밍으로 해당 위치까지 도착했을 때의 가장 큰 합을 저장한다.

n = int(input())
perms = list(map(int,input().split()))
max_add = [0 for _ in range(n)]
max_add[0] = perms[0]
for i in range(1,n):
    if perms[i] > max_add[i-1] + perms[i]:
        max_add[i] = perms[i]
    else:
        max_add[i] = max_add[i-1] + perms[i]
print(max(max_add))