CF513E2.Subarray Cuts

You are given an array of length n and a number k. Let's pick k non-overlapping non-empty subarrays of the initial array. Let s__i be the sum of the i-th subarray in order from left to right. Compute the maximum value of the following expression:

|_s_1 - _s_2| + |_s_2 - _s_3| + ... + |s__k - 1 - s__k|

Here subarray is a contiguous part of an array.

给你一个长度为 $n$ 的数组和一个数 $k$。请从原数组中选出 $k$ 个互不重叠的非空子数组。设 $s_i$ 表示从左到右第 $i$ 个子数组的元素和。请计算下列表达式的最大值：

$$|s_1 - s_2| + |s_2 - s_3| + \ldots + |s_{k-1} - s_k|$$

其中，子数组是指数组的一个连续部分。

The first line of input contains two integers n and k. The second line contains n integers — the elements of the array. The absolute values of elements do not exceed 104.

The problem consists of two subproblems. The subproblems have different constraints on the input. You will get some score for the correct submission of the subproblem. The description of the subproblems follows.

• In subproblem E1 (9 points), constraints 2 ≤ n ≤ 400, 2 ≤ k ≤ min(n, 50) will hold.
• In subproblem E2 (12 points), constraints 2 ≤ n ≤ 30000, 2 ≤ k ≤ min(n, 200) will hold.

输入的第一行包含两个整数 $n$ 和 $k$。第二行包含 $n$ 个整数——即数组的元素。所有元素的绝对值不超过 $10^4$。

本题包含两个子问题。这两个子问题对输入的约束条件不同。正确提交每个子问题可获得相应分数。子问题的描述如下：

• 子问题 E1（9 分）：约束条件为 $2 \leq n \leq 400$，$2 \leq k \leq \min(n, 50)$。
• 子问题 E2（12 分）：约束条件为 $2 \leq n \leq 30000$，$2 \leq k \leq \min(n, 200)$。

Output a single integer — the maximum possible value.

输出一个整数——最大可能的值。

Consider the first sample test. The optimal solution is obtained if the first subarray contains the first element only, the second subarray spans the next three elements and the last subarray contains the last element only. The sums of these subarrays are 5, 9 and 1, correspondingly.

Consider the second sample test. In the optimal solution, the first subarray consists of the first two elements and the second subarray consists of the third element only. Note that the last element does not belong to any subarray in this solution.

考虑第一个样例测试。最优解为：第一个子数组仅包含第一个元素，第二个子数组覆盖接下来的三个元素，最后一个子数组仅包含最后一个元素。这些子数组的和分别为 $5$、$9$ 和 $1$。

考虑第二个样例测试。在最优解中，第一个子数组由前两个元素组成，第二个子数组仅由第三个元素组成。注意：在此解中，最后一个元素不属于任何子数组。