[백준(baekjoon) 1912] 연속 합

문제 백준 1912 n(1…100,000)과 n의 크기를 가진 수열이 주어질 때, 연속된 숫자들의 합 중 최대 값을 출력하라. 예시 : {10, -4, 3, 1, 5, 6, -35, 12, 21, -1}일 때, 12+21인 33이 정답이 된다. 해결 간단하게 앞에서 부터 시작해서 각 값으로 끝나는 연속된 수열의 최대 합을 구하면 된다. 자신으로 시작하는 경우 이전 연속 수열에 자신을 포함하는 경우 이렇게 두 가지의 경우로 나눌 수 있으므로, 두 값을 비교해서 큰 값을 저장하면 된다. 시간복잡도는 O(N)이다. 알고리즘 DP로 풀었고, bottom-up 방식이랑 top-down 방식으로 각각 풀었다. DP에 대해 아직 잘 모른다면 여기의 알고리즘 부분을 보자. 구현 java Top-down 방식 1.imp..

2018.07.08