1912(DP)

풀이1

리스트에서 연속된 값들을 뽑아 최댓값을 만들어야 하므로 순서대로 연속해서 더해가면서 더한 값들을 다른 리스트에 저장하고 마지막에 거기서 최대값을 뽑으면 될 것 같다.

-> 경우의 수가 너무 많다. 두개가 연속된 수, 세개가 연속된 수 이런식으로 구하면 n!이 될듯

풀이2

리스트 크기만큼 반복문을 돌며 누적합과 해당 인덱스에서 누적한 값을 비교해서 현재 인덱스(누적한 값)의 값이 더 크다면 그냥 현재 값부터 다시 누적을 시작하는게 이득이니까 누적값(현재 인덱스까지 합한 값)과 현재 인덱스를 비교해서 누적값이 더 크다면 리스트의 현재 인덱스 값을 누적값으로 갱신해준다.

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


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

print(max(dp))

dp -> 말로 설명되는 점화식을 생각해보고 그대로 코드에 옮겨보기