백준 알고리즘 - 연속합 (1912) [Python]

문제 www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 상황 - 주어진 수열에서 합이 가장 큰 연속 부분 수열의 합을 구하는 문제이다. 해결 전략 1 - 범위가 100,000이므로 O(N^2)는 100억으로 속도 이슈가 발생하여 O(N) 혹은 O(NlogN)의 범위 안에서 작동하여야 한다. - cache를 어떻게 정의하느냐가 문제의 포인트이다. - 0부터 i 사이의 구간에서 i로 끝나는 연속 부분합 중 최대의 값을 저장한다. 코드 1 2 3 4 5 6 7 8 9 1..
알고리즘 학습/백준 알고리즘 2020. 9. 21. 16:22
1