[Python] 백준 1912 : 연속합

 

1. 문제

 

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

1912번: 연속합

 

 

---

 

 

2. 접근

 

연속합은 동적계획법이나 분할정복 등의 여러 알고리즘으로 구할 수 있는데, 그 중 시간복잡도가 가장 낮은 동적계획법으로 구현했다.

 

 * 동적계획법이 아닌 다른 알고리즘은 아래에 참고하면 된다.

 

https://2nnsv.tistory.com/40

[알고리즘] 연속 부분 수열의 합

 

 

---

 

3. 코드

 

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

def DynamicProgramming(arr):
    cache = [None] * len(arr)
    cache[0] = arr[0]
    for i in range(1, len(arr)):
        cache[i] = max(0, cache[i-1]) + arr[i] 
    return max(cache)

print(DynamicProgramming(arr))