将数组划分为k个子集，最小化各子集最大值×元素数量的差值

问题定义 #

给定数组arr和划分数量k，需将数组拆分为k个非空子集，目标是让所有子集的最大值×子集元素数量这一指标的最大差值尽可能小。

核心解法思路 #

• 先排序，再连续分段：这是解决这类问题的最优策略之一
  1. 把数组按升序排序，让数值相近的元素集中在一起，避免大元素和小元素混组导致乘积剧烈波动。
  2. 将排序后的数组划分为k个连续子数组，从均匀分配元素的初始方案开始，微调相邻段的元素数量，计算每段的乘积值，找到这些值的最大差值最小的划分方式。
• 为什么连续分段最优？如果把大元素和小元素混合分组，子集的最大值会被大元素拉高，同时元素数量增加会进一步推高乘积，反而会让不同子集的乘积差值更大，远不如连续分组的效果稳定。

示例验证 #

输入：arr = [5,6,7,8,9,1,2,3,4]，k = 3
排序后数组：[1,2,3,4,5,6,7,8,9]
最优划分：[[1,2,3,4],[5,6,7],[8,9]]
各子集乘积计算：

• 子集1：4 × 4 = 16
• 子集2：7 × 3 = 21
• 子集3：9 × 2 = 18
  乘积的最大值为21，最小值为16，差值为5，这是当前能得到的最小差值。

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