题目：最大子数组和的划分

描述

给定一个长度为 $n$ 的整数数组 $A$，以及一个整数 $k$。

你需要将数组划分成若干个连续的子数组，每个子数组的长度 至多 为 $k$。对于每个子数组，你可以选择将该子数组内的所有元素 全部取反（即每个元素乘以 $-1$）或保持不变。

划分并选择取反操作后，所有子数组的和的总和需要达到最大。请计算该最大可能的总和。

输入

• 第一行包含两个整数 $n$ 和 $k$ ($1 \leq k \leq n \leq 10^5$)。
• 第二行包含 $n$ 个整数 $A_1, A_2, \dots, A_n$，其中 $|A_i| \leq 10^4$。

输出

• 输出一个整数，表示通过最佳划分和取反操作后可以获得的最大总和。

示例

输入

5 2
1 -2 3 -4 5

输出

9

解释

一种可能的划分和操作方式：

1. 子数组 [1, -2]：保持不变，和为 $1 + (-2) = -1$
2. 子数组 [3, -4]：取反，变为 [-3, 4]，和为 $-3 + 4 = 1$
3. 子数组 [5]：保持不变，和为 $5$

总和为 $-1 + 1 + 5 = 5$。然而，通过其他划分和操作可以获得更大的总和，例如：

1. 子数组 [1]：保持不变，和为 $1$
2. 子数组 [-2, 3]：取反，变为 [2, -3]，和为 $2 + (-3) = -1$
3. 子数组 [-4, 5]：取反，变为 [4, -5]，和为 $4 + (-5) = -1$

总和为 $1 + (-1) + (-1) = -1$，这并不是最佳方案。最佳方案需要通过动态规划、贪心策略和前缀和来找到最优的划分和取反操作，从而达到最大总和 $9$。

提示

• 由于 $n$ 可以达到 $10^5$，需要设计高效的算法，建议使用动态规划结合前缀和进行优化。
• 贪心策略可以用于在划分子数组时决定是否取反以最大化当前子数组的和。

感觉这道题很奇怪啊