[Python] 백준 1912번: 연속합 풀이

 

소스코드

n = int(input())
A = list(map(int, input().split()))
dp = [x for x in A]

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

 

처음에는 이중 for 문으로 풀었는데, 시간 초과가 나와서 '아 이렇게 푸는게 아니구나' 하는 생각에 싹 갈아엎었다.

다시 생각해보니 매우 간단했다. 그냥 한 칸 이전의 dp값이랑 자신의 수랑 더하는게 큰지, 그냥 안더하고 놔두는게 큰지 비교하기만 하면 된다. 그래서 시간복잡도가 O(n) 으로 매우 간단하다.