[BaekJoon] "DP" - 백준 1912번 문제 : 연속합

[문제 설명]

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

1912번: 연속합

 

n개의 정수로 이루어진 임의의 수열이 주어짐

이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 함 (단, 수는 한 개 이상 선택)

예제 입력)

10
10 -4 3 1 5 6 -35 12 21 -1

 

예제 출력 --> 12+21 = 33이 출력 되어야 함

 

[해결 로직]

이 문제는 dp 알고리즘으로 해결 가능함

처음에 코드를 작성할 때는 이중 반복문으로 코드를 작성하였는데, 

dp 알고리즘으로 반복문 한번만 실행하면 됨..

 

두 번째 요소 부터 현재 값과 현재값+이전값 을 비교하여 더 큰 값을 현재 값에 저장

이렇게 하면, 이전부터 숫자가 커질 때마다 합을 저장하게 됨

만약 이보다 작은 숫자가 나온다면? 더하지 않으면 됨 --> 연속적이지 않은것으로 의미

 

이렇게 해서 최종적으로 리스트에 저장된 가장 큰 값을 불러오면, 연속합 중 가장 큰 합의 수를 가져오는 것이 됨

 

[Solution 코드]

from collections import deque

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

## 그냥 이전합까지 계산한거를 현재 숫자랑 더하고, 더 큰 값을 넣으면 됨..
## 나만 어렵게 푼듯..내꺼는 반복문을 두번 돌아야 하니까나 시간 초과 난듯

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

print(max(ary))