백준 1912번 파이썬 문제풀이(DP - 연속 합)

---

N = int(input())

input_array = list(map(int, input().split()))
dp = [input_array[0]] * N

for i in range(1, N):
    dp[i] = max(dp[i - 1] + input_array[i], input_array[i])

print(max(dp))

->원리는 간단하다. 기존 dp문제처럼 최댓값을 계속 dp배열에 넣어서 새로운항이 나오면 전에 저장되어있던 최댓값에서 그 새로운항의 값을 더한 값이 기존의 최댓값보다 크다면 그값을 저장해주면 되는 방식이다.  

 

이문제는 간단하면서도 어렵지 않은 문제인데도 불구하고 정답률이 낮은것을 보고 쉽게 생각하지 못해 이중반복문으로 풀려고 해서 계속 시간초과가 발생했다. ㅠ