728x90 반응형 백준 19121 [백준 1912][파이썬] 연속 합 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 연속된 몇 개의 정수를 골라 합이 가장 큰 값을 구해야한다. 일단 가장 간단한 알고리즘을 생각해보면 이중 반복문으로 모든 연속된 부분 수열의 합을 구하는 것이다. 물론 이 방법으로 구현하게 되면 시간 초과가 발생한다. 조금 더 시간을 단축하는 알고리즘을 사용해야한다. 일단 기본적으로 dp[i]에 입력받은 수열의 인덱스 0부터 i까지의 부분 수열의 합을 저장한다. 이렇게 구하다가 어느 조건을 만족하면 인덱스의.. 2023. 1. 13. 이전 1 다음 728x90 반응형
