题解

思路

用前缀和 $s$ 在 $O(1)$ 时间求任意长度 $m$ 段的和。令 $dp[j][i]$ 表示在前 $i$ 个元素中恰好选择 $j$ 段的最大和。不可达状态初始化为负无穷，且 $dp[0][i]=0$。

做法

对每个 $j=1\ldots k$、$i=1\ldots n$，有两种选择：

1. 不选位置 $i$，沿用 $dp[j][i-1]$；
2. 让一段恰好在 $i$ 结束。该段为 $[i-m+1,i]$，此前的 $j-1$ 段必须位于前 $i-m$ 个位置，所以用 $dp[j-1][i-m]+s_i-s_{i-m}$ 转移。

取两者最大值，答案为 $dp[k][n]$。所有和与状态都必须使用 64 位整数。

正确性证明

对 $j$ 与 $i$ 归纳。任意前 $i$ 个元素内恰好选择 $j$ 段的最优方案中，位置 $i$ 要么未被选择，此时方案完整地属于 $dp[j][i-1]$；要么被选择，此时包含它的最后一段只能是 $[i-m+1,i]$，其余 $j-1$ 段完全位于前 $i-m$ 个位置，最优值正是第二项转移。两类情况互斥且覆盖全部合法方案，因此取最大值后 $dp[j][i]$ 正确。由归纳可知 $dp[k][n]$ 是恰好选择 $k$ 段的最大总和。

复杂度分析

时间复杂度 $O(nk)$。每一层只依赖上一层，使用滚动数组后空间复杂度为 $O(n)$。