2023.05.25 풀이
import sys
input=sys.stdin.readline
n=int(input())
arr=list(map(int, input().split()))
d=[0]*(n)
d[0]=arr[0]
for i in range(1, n):
d[i]=max(arr[i], d[i-1]+arr[i])
print(max(d))- d[0]=arr[0],
d[1]~d[n]은 arr 본인 값과 그 전까지의 합(최댓값) 중에 큰 값
다른 풀이
--
check point
- 역시 점화식 부분이 어려웠으나,
해당 값에 왔을 때 최댓값이 되려면 어떻게 해야하는지를 생각해보기
d[0], d[1], d[2] ... 차례로 답을 찾으면서 규칙 찾아보기 - 이전까지의 최댓값과 현재의 값 비교해서 큰 값이 해당 값이 됨
