백준 1912 파이썬 (연속합)

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

💻 Code

n = int(input())
data = list(map(int, input().split()))
dp = []
csum = 0

for num in data:
    csum = csum + num
    dp.append(csum)
    if(csum < 0):
        csum = 0
  
print(max(dp))

• 처음부터 끝까지 계속 더해준 값을 dp에 저장하였다
• 연속합 값이 음수가 나올 경우 0으로 초기화
• 

---

➕ 더 똑똑하게 푸는 방법이 있을거 같아서 구글링을 해보았다.

n = int(input())
a = list(map(int, input().split()))
sum = [a[0]]
for i in range(len(a) - 1):
    sum.append(max(sum[i] + a[i + 1], a[i + 1]))
print(max(sum))

• 결과는 위 이미지랑 똑같다 (a 가 data, sum이 dp)
• sum = [a[0]] : 비교를 위해 sum리스트에 초기값으로 a[0]을 삽입
• max(sum[i] + a[i + 1], a[i + 1] : 기존값에 다음값을 더한 값과 그냥 다음 값 중에 큰 수를 저장