循环数组连续元素的最小差两子集划分（子集和变种）

这个问题是经典子集和问题的一个有意思的变种，咱们先把核心要求和约束理清楚：给定一个由正整数组成的循环数组（首尾元素视为连续），需要将它分割成两个由连续元素构成的子集，最终让两个子集的元素和差值尽可能小。

关键约束 #

• 两个子集的元素都必须是原数组中的连续元素
• 数组是循环结构——最后一个元素的下一个元素是第一个元素，反之亦然

示例演示 #

示例1 #

输入数组：[7,5,1,3,8,9,11,8]
输出结果：0

最优拆分：子集1取连续元素 {11,8,7}（利用数组循环特性，8之后衔接第一个元素7），子集2取剩余的连续元素 {5,1,3,8,9}。两个子集的元素和均为26，差值为0，这是最理想的结果。

示例2 #

输入数组：[10,14,75,90,3,5,40,4,8]
输出结果：27

最优拆分：子集1取连续元素 {4,8,10,14,75}，子集2取剩余的连续元素 {90,3,5,40}。计算可得两者的和差为27，这是当前数组能达到的最小差值。

核心解决思路（供参考） #

因为数组是循环的，我们可以把原数组拼接成arr + arr的形式，这样就能把循环的连续子集转化为线性数组中的连续窗口。具体步骤如下：

1. 先计算原数组的总元素和total_sum
2. 遍历所有可能的窗口长度（从1到n-1，n是原数组长度），每个窗口对应一个连续子集的和current_sum
3. 另一个子集的和就是total_sum - current_sum，计算两者的绝对差值，记录最小的那个值
4. 注意窗口不能超过原数组长度n，因为两个子集是互补的，不需要重复计算

这样就能高效找到最小的和差啦。

内容的提问来源于stack exchange，提问作者dituoa