如何划分实数序列以最大化乘积和，满足每组元素不超过t个

已验证边界场景最优策略 #

• 所有元素属于[0,1]区间：全部单独分组即可，该区间内任意两个数a,b都满足a*b ≤ a + b，合组不会带来收益提升
• 所有元素属于[2,+∞)区间：将元素降序排序后，每t个划分为一组，剩余不足t个的单独成组即可。该区间内数相乘的增益恒大于拆分求和的收益，且大数优先合组的收益最高

[1,2]区间通用解法 #

该区间的核心矛盾是k个元素相乘的收益是否超过拆分求和的收益，阈值随数值变化没有固定规则，推荐用动态规划解决：

1. 先将所有元素降序排序，该排序规则的最优性可通过交换不等式证明：大数优先合组的收益永远不会低于小数优先合组的收益
2. 定义dp[i]为前i个元素能得到的最大乘积和，边界条件为dp[0] = 0
3. 状态转移方程：dp[i] = max( dp[i - k] + product(nums[i - k ... i - 1]) )，其中k的取值范围为1 ≤ k ≤ min(t, i)，即对每个位置i，枚举所有符合长度要求的分组可能，取收益最大值

以t=3为例：三个1.01的场景下，动态规划会计算出1.01*3=3.03大于1.01^3≈1.03，选择k=1的拆分方案；三个1.99的场景下，1.99^3≈7.88大于1.99*3=5.97，自动选择k=3的合组方案，不需要手动计算阈值
如果t的取值较小（≤100），该方案的时间复杂度O(n*t)完全可以支持万级以上数据量的计算需求。

任意实数场景通用解题方向 #

如果集合包含负数、0等特殊值，需要对方案做以下调整：

1. 先将元素按类型分类：≥1的正数、(0,1)区间的数、负数、0
2. 排序规则调整：正数按降序排列，负数按升序排列（让绝对值大的负数优先合组，两个负数相乘得正的收益更高）
3. 动态规划状态扩展：除了记录前i个元素的最大乘积和，还要记录前i个元素的最小乘积和，负数相乘会让最小值转换为最大值，转移时需要同时考虑两种状态
4. 0的特殊处理：0单独分组的贡献为0，仅当剩余元素合组的乘积为负时，加入0合组才能提升收益，其余场景0单独分组即可

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