BOJ 12846 무서운 아르바이트

BOJ 6549 히스토그램에서 가장 큰 직사각형 문제와 똑같은 문제라고 보면 된다.

문제를 설명하자면, 
아르바이트가 있는데, 날마다 급여가 정해져있고, 한 번 일하기 시작하면 중간에 빠질 수 없고(즉 연속으로 며칠을 일해야 한다), (그 연속으로 일한 날들마다의 급여 중에서 가장 작은 값)* (근무 일수)가 받을 수 있는 급여가 된다.

각 날마다의 급여가 주어지면, 언제부터 언제까지 일을하는 것이 급여를 최대로 받을 수 있는지를 구하는 문제이다. 받을 수 있는 최대 급여를 구해서 출력하는 문제이다.

분할 정복(+세그먼트 트리)의 방법과, stack을 이용하는 방법이 있다.
참고하면 좋은 문제는 히스토그램 문제이고, 풀이는 -> baekjoon online judge blog