[Baekjoon] 1912번 : 연속합 (Python)

[Baekjoon] 1912번 : 연속합 (Python)

 

목차

 

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

1912번: 연속합

Python

 

방법 1 - 메모리 38568KB / 시간 136ms / 코드 길이 133B

 

DP의 Memorization을 통한 연속된 값에 대한 최대값구하기 이다.

다만 $O(n^2)$ 즉, for문을 2번쓰면 시간초과가 나니 주의.

 

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

방법 2 - 메모리 38568KB / 시간 100ms / 코드 길이 214B

일반적인 DP와 달리 for문을 통한 즉각적인 값을 구하는 방법이 존재한다.

물론 이것은 연속적인 값을 구하는 문제의 특수성 때문에 가능한 방법이다.

 

우선 들어가기에 앞서 기입받는 정수들의 값들이 모두 음수로면 그 중 가장 큰 값을 출력한다.

그 외 양의 정수가 하나라도 존재한다면 t를 통한 연속적인 값들을 더한다. 다만 만약 음수가 나온다면 0으로 돌린다.

0으로 돌리는 것이 가능한 것은 list에는 양의 정수가 존재한다는 조건문 가정이 있었기 때문에 가능한 것입니다.

이를 통해 최대값은 m에 저장하고 최후의 m만으로 결과를 도출받을 수 있습니다.

 

input()
a = list(map(int,input().split()))
if max(a) <= 0: print(max(a))
else:
    t = 0
    m = 0
    for i in a:
        t += i
        if t < 0:
            t = 0
        if m < t:
            m = t
    print(m)