오늘의 회고

오랜만에 DP 문제인 연속합을 풀었다.

---

풀이

DP 문제는 3가지 방법을 거쳐서 풀고 있다.
참고) 바킹독님

DP 푸는 과정
1. 테이블 정의하기
2. 점화식 찾기
3. 초기값 정하기

1. 테이블 정의하기

dp[n] = > index n까지 숫자 합 중 최댓값

2. 점화식 찾기

dp[1] = max(dp[0], dp[0]+dp[1])
dp[2] = max(dp[1], dp[1]+dp[2])
이전 값에서 내 숫자를 더하는 게 큰지 그대로 냅두는 게 큰지 확인!

3. 초기값 정하기

사실 list를 입력 받고 dp 테이블을 따로 생성해줬으면

dp[0] = arr[0] 

이렇게 초기값이 필요할텐데 나는 arr 테이블로 입력 받고 arr 테이블 자체를 dp테이블처럼 사용했다.

---

코드

import sys
input = sys.stdin.readline

# dp[n] = > 인덱스 n까지 숫자 합 중 최댓값

n = int(input())
arr = list(map(int, input().split()))

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

print(max(arr))