[백준 1912][파이썬] 연속 합

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

1912번: 연속합

연속된 몇 개의 정수를 골라 합이 가장 큰 값을 구해야한다.

 

일단 가장 간단한 알고리즘을 생각해보면 이중 반복문으로 모든 연속된 부분 수열의 합을 구하는 것이다.

 

물론 이 방법으로 구현하게 되면 시간 초과가 발생한다.

 

조금 더 시간을 단축하는 알고리즘을 사용해야한다.

 

일단 기본적으로 dp[i]에 입력받은 수열의 인덱스 0부터 i까지의 부분 수열의 합을 저장한다.

 

이렇게 구하다가 어느 조건을 만족하면 인덱스의 시작 위치를 바꿔서 dp[i]에 바뀐 시작 위치부터 i까지의 합을 저장해야한다.

 

이러한 조건을 찾아야한다.

 

처음 생각한 조건은 다음과 같다.

 

음수가 존재하는 인덱스를 기준으로 시작 위치를 바꾼다.

 

부분 수열이 모두 양수일 경우 무조건 길이가 길어야 최댓값이 나오기 때문에 이렇게 생각을 했다.

 

그러나 음수를 포함시키더라도 앞 뒤로 연속되어있는 부분 수열의 합이 최댓값이 나올 수도 있다.

 

예를 들어 (10, 6, -4, 5)라는 수열이 존재한다고 하면 (10, 6)의 합은 16이고 (10, 6, -4, 5)의  합은 17이다.

 

이러한 점을 고려하면 시작 위치를 바꾸는 조건은 다음과 같이 설정해야한다.

 

i까지의 합이 수열의 인덱스 i에 해당하는 값보다 작을 때 시작 위치를 바꾼다.

 

즉 i까지의 합이 수열의 인덱스 i에 해당하는 값보다 작다면 이 부분수열을 이어붙이는 것이 오히려 값을 작게 만든다.

 

그 인덱스 i부터 시작해서 다시 합을 구해야한다.

 

이렇게 구한 dp 리스트에서 가장 큰 값이 답이 된다.

 

위 조건을 좀 더 직관적으로 바꾸면 아래와 같다.

 

i-1까지의 합이 0보다 작을 때 시작 위치를 바꾼다.

n=int(input())
dp=list(map(int, input().split()))
for i in range(1, n):
    if dp[i-1]>0:
        dp[i]+=dp[i-1]
print(max(dp))