题解

问题分析

题目要求将数组划分为 $k$ 个连续非空子段，使得最大子段和与最小子段和的差值最大。

关键观察

1. 最大化不平衡度 = 最大化最大子段和 - 最小子段和
2. 由于所有元素非负，最大子段和可以通过合并多个元素获得
3. 最小子段和可以通过单个小元素获得

算法思路

分类讨论法：

情况1：$k = 2$

• 只有一种划分方式：在某个位置 $i$ 切一刀
• 不平衡度 = $|s[i] - (s[n] - s[i])| = |2s[i] - s[n]|$
• 遍历所有分割点取最大值

情况2：$k \geq 3$

策略：让一个子段尽可能大，另一个子段尽可能小

三种可能的最优方案：

1. 最小子段在中间：

   • 选择一个元素 $a[i]$ 作为单独子段（最小值）
   • 左边取尽可能长的连续段（但不能太长以免影响段数）
   • 右边取尽可能长的连续段
   • 不平衡度 = $(s[i] - s[l] + s[r] - s[i+1]) - a[i]$

2. 最小子段在两端：

   • 使用滑动窗口找长度为 $(n-k+1)$ 的最大子段和
   • 最小子段是剩余部分中的最小值
   • 不平衡度 = 最大窗口和 - 剩余部分的最小值

核心代码逻辑

$k = 2$ 的情况

for (int i = 1; i < n; i++) {
    ans = std::max(ans, std::abs(s[i] * 2 - s[n]));
}

$k \geq 3$ 的情况

1. 中间最小段：

   // 左边连续段 + 右边连续段 - 中间单独段
   ans = std::max(ans, s[i] - s[l] + s[r] - s[i+1] - a[i]);
   

2. 两端最小段：

   // 长度为(n-k+1)的最大窗口和 - 剩余部分的最小值
   ans = std::max(ans, s[r] - s[l] - std::min(pre[l], suf[r]));
   

复杂度分析

• 预处理：$O(n)$ 计算前缀和、前缀最小值、后缀最小值
• $k=2$：$O(n)$ 遍历分割点
• $k\geq3$：$O(n)$ 遍历所有可能的最小子段位置
• 总复杂度：$O(n)$

算法步骤

1. 读入 $n, k$ 和数组 $a$
2. 计算前缀和数组 $s$
3. 根据 $k$ 值选择不同策略：
   • $k=2$：遍历分割点计算差值
   • $k\geq3$：
     • 考虑中间最小段的情况
     • 考虑两端最小段的情况
4. 输出最大不平衡度

算法标签

• 贪心算法
• 前缀和
• 滑动窗口
• 分类讨论
• 最优化问题