[백준 1912] 연속합 (Python)

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

1912번: 연속합

[문제]

 

[틀린 코드]

n = int(input())

num = list(map(int, input().split()))
arr = []
for i in range(1, n):
    for j in range(0, n-i):
        arr.append(sum(num[j:(j+i)]))

print(max(arr))

처음에는 리스트 슬라이싱을 이용해서 모든 경우를 구한 뒤 가장 합이 큰 경우를 출력하였다.

이렇게 문제를 푸니 테스트케이스는 맞지만 시간초과로 틀렸다.

그래서 다른 사람의 코드를 참고하여 풀게되었다.

 

[맞은 코드]

n = int(input())

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

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

print(max(num))

전형적인 DP 알고리즘 코드였다.

앞의 수와 더한 값과 더하지 않은 값 중 더 큰 값을 저장하고 이를 계속 하면 결과가 누적되어 최종 결괏값을 알 수 있다.