백준 1912번

(Python) 백준 1912번 - 연속합

문제 링크: https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 Dynamic Programming 문제답게 코드 구현보다는 문제 해결을 위한 아이디어를 생각하는 것이 더 어려운 문제이다. 문제 해결을 위한 아이디어는 다음과 같다. 우선 해당 인덱스까지의 최대값을 담을 배열을 선언한다. 그 후 처음부터 순회하며 해당 인덱스까지의 최대값을 계산하고 이를 저장한다. 해당 인덱스까지의 최대값은 이전 인덱스에서의 최대값 또는 현재 인덱스의 값이 된다. 최종적으..