[백준] 1912번: 연속합 - python

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

1912번: 연속합

 

구간의 최대 연속합을 구하는 문제

저장소를 만들어 현재까지의 최대 연속합을 저장해 나가면서 풀면 된다.

여기서 최대 연속합이 되는 경우는 3가지 경우인데 

 

첫번째 경우는 -1 3 처럼 3이 현재값이 최대인경우 

두번째는 3 2 처럼 전의 최장합과 바로 앞 원소가 더해져야 최대인 경우

세번째는 -1 2 3 처럼 자기 자신과 그 전 원소가 최대인 경우

 

이 모든 경우를 저장하며 끝까지 이어나간다음 dp의 최대값을 도출하면 된다.

 

n = int(input())

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


dp = [0] * (n)

dp[0] = arr[0]
for i in range(1, n):
    dp[i] = max(dp[i-1] + arr[i], arr[i-1]+arr[i], arr[i] )
    #이전 최장합과 연결, 자신 바로 앞 원소과 연결, 자기 자기자신 이  3가지 경우만 존재
print(max(dp))

 

완성