https://www.acmicpc.net/problem/25188
문제요약
- 숫자들을 6개의 연속구간으로 나누고(구간이 비어도됨. 겹치는 것은 안됨)
- 1, 3, 5 구간 숫자들의 합을 최대로
접근법
- x 부터 시작하는 두개 구간의 합의 최대값은 O(n)에 구함
- 왼쪽끝부터 max, 오른쪽 끝부터 max(단 오른쪽 끝부터 max는 미리 구해놓음)
- 1번구간을 늘려가면서 3개 구간 합의 최대값을 구함
- 빈 구간이 가능하기 때문에 어떻게 하든 왼쪽이 연속이면 1, 3, 5 구간이 만들어짐
O(N) 풀이법?????
newbieski