[알고리즘][백준] 1912번 연속합 - 파이썬(python) 풀이

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

1912번: 연속합

---

 

# # sol 1
import sys

# 정수 및 수열
n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))

# dp - n까지의 연속합 중 max
d = [0] * n
d[0] = a[0]

# 현재값 VS 이전까지의 합 + 현재값
for i in range(1, n):
    d[i] = max(a[i], d[i-1] + a[i])

print(max(d))

 

따로 dp 리스트를 만들지 않고 입력받았던 수열 리스트에 바로 적용하는 경우도 있었다

 

# # sol 2

import sys

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))

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

print(max(a))

 

 

메모리 및 시간은 똑같게 나오긴 하다