25414번 - 구간 나누기

$N$개의 수 $A_1, A_2, \cdots , A_N$이 주어진다. 이 때 서로 겹치지 않는 연속한 구간을 정확히 $K$개를 잡아 각 구간 점수의 합을 구했을 때, 가능한 값의 최댓값을 구하는 프로그램을 작성하라.

이 문제에서 어떤 구간의 점수는 구간에 속한 수의 최댓값과 최솟값의 차이와 같다.

문제를 정확하게 정의하면 다음과 같다.

다음을 만족하는 $2K$개의 정수 $s_1, e_1, s_2, e_2, \cdots , s_K, e_K$ ($1 ≤ s_1 ≤ e_1 < s_2 ≤ e_2 < \cdots ≤ s_K ≤ e_K ≤ N)에 대해 다음을 최대화하라.

$$\sum_{k=1}^{K}{p(s_k,e_k)}$$

단,

$$p(s, e) = \max{(A_s, \cdots, A_e)} - \min{(A_s, \cdots, A_e)}$$

첫 번째 줄에 두 정수 $N$ ($1 ≤ N ≤ 2 \times 10^5$)과 $R$ ($1 ≤ R ≤ \min{(200, N)}$)가 공백으로 구분되어 주어진다. 당신의 프로그램은 $1 ≤ K ≤ R$ 범위의 모든 $K$에 대한 답을 출력해야 한다.

두 번째 줄에 $N$개의 정수 $A_1, A_2, \cdots , A_N$ ($1 ≤ A_i ≤ 10^9$)이 순서대로 공백으로 구분되어 주어진다. 이 중 $i$번째로 주어지는 수가 $A_i$이다.

총 $R$개의 줄에 걸쳐 답을 출력한다. $i$번째 줄에는 $K = i$일 때의 답을 출력한다. 즉, $A$에서 서로 겹치지 않는 연속한 구간을 정확히 $i$개를 잡아 각 구간 점수의 합을 구했을 때 가능한 값의 최댓값을 출력한다.

$K = 1$: [2, 3]의 한 구간을 잡으면 최적이다.

$K = 2$: [1, 2], [4, 5]의 두 구간을 잡으면 최적이다.

$K = 3$: [1, 2], [3, 4], [5, 6]의 세 구간을 잡으면 최적이다.