业余的业余

abababa 基本已经给出了完整的算法。

定义:
整数的互异拆分: 对正整数 $n$， 从集合 $\{1,2,3, \cdots, n\}$ 中选择一个非空子集，使得该子集 $S$ 的元素和为 $n$， 则称集合 $S$ 为 $n$ 的一个 互异拆分

最大积互异拆分: 在 $n$ 的所有互异拆分中，使得集合$S$ 中所有元素的乘积最大的互异拆分,称为$n$的最大积拆分。

结点: 对正整数 $n$, 如果存在正整数 $m$, 使得 $\displaystyle n=\sum_{i=2}^{m+1}$, 则称 $n$ 为一个结点。在需要区分结点时，也称 $n$ 为第$m$个结点。显然，第 $m$ 的结点是结点的无穷集合 $\{2,5,9,14,20,\cdots\}$ 中的元素按从小到大排序的序号。

命题1: 当$n>1$ 时，其最大积拆分不含元素$1$. 用反证法易证，证略。

命题2: 如果 $n$ 是第 $m$ 个结点， 那么$n$ 的最大积拆分是 $\{2,3,\cdots,m+1\}$ 证略。

命题3：如果 $n$ 是第 $m$ 个结点和第 $m+1$ 个结点之间的整数(不包含), 那么其最大积拆分中有 $m$ 个元素 (就低不就高)。特别的，记第$m+1$ 的结点对应的整数为 $p$, 如果 $p-n>1$, 那么$n$ 的最大集拆分是 $p$ 的最大集拆分去掉 $p-n$ 后的集合；如果 $p-n=1$ 那么 $n$ 的最大积拆分是 $p$ 的最大集拆分中去掉 $2$和$m+2$， 加入 $m+3$后得到的集合。

业余的业余

命题3的证明可以用这样的思路。$n$的任一 $m$ 个元素的拆分 $T$，可以以相邻集合两两不同的方式组成一个链条，从 $T$按积单调增加的方式 走到最大积互异拆分。因为相邻集合仅两个元素不同，设分别为 a,b 和 c,d. 显然有 a+b=c+d. 而最大积拆分可以保证a,b（或c，d)之差为最小（a,b,c,d中的最大数最小)，从而使积更大。

业余的业余

似乎这样更好走通:

首先，对足够大的 $n (n\ge 2)$, 互异拆分中不能含 $1$， 以下讨论都隐含互异拆分中不含元素 $1$ 这一条件。互异拆分中的数按从小到大排列，称第 $i$ 个元素和 第 $i+1$ 的元素为相邻元素。则

定义: $n$ 的 $m$-最大积互异拆分, 是这样一个集合:
1.它的所有元素都是大于$1$的正整数，且两两不同;
2. 它的基数为 $m$
3. 它所有元素之和为 $n$
4. 在所有满足前面3个条件的集合中，它的所有元素之积最大。

断点: 设 $\{a_1, a_2,\cdots, a_m\}$ 是一个互异拆分，且 $a_i<a_{i+1}\forall 1\le i <m$。 如果  $a_{k+1}-a_k>1 (1\le k <m)$， 则称两元素间有一个断点。

命题1': m-最大积互异拆分相邻元素之差不大于 $2$.
证明: 反证法。设 $a_1, a_2, ..., a_m$ 构成 $n$ 的$m$-最大积互异拆分，且  $a_{i+1}-a_i>2 (0\le i<m)$, 那么可以通过把 $a_i$加$1$， $a_{i+1}$减$1$ 得到 $n$ 的另一个合法的$m$-互异差分，且新拆分与原拆分元素积之比$=\frac{(a_i+1)(a_{i+1}-1)}{a_i a_{i+1}}>1$( 因为 $(a_i+1)(a_{i+1}-1)-a_i a_{i+1}=a_{i+1}-a_i-1>0$), 这与原拆分是最大积互异拆分的题设矛盾。故假设不成立，命题为真。

命题2': 最大积互异拆分中不能含有多于一个断点.
证明方法与上面相似，略。举个例子说明 $\{2,3,(断点)5,6,(断点)8,9\}$, 替换为$\{2,4,5,6,7,9\}$ 显然得到更大积 $(3\times 8<4\times 7)$. 而后者显然任然不是最大积互异拆分，因为依然有两个断点.


命题3': 假定 $n$ 存在 $m$-互异拆分和 $(m+1)$-互异拆分，则其 $(m+1)$-最大积互异拆分的元素积大于其$m$-最大积互异拆分的元素积。
设 $\{a_1, a_2,\cdots,a_m\}$ 是$n$ 的$m$-最大积拆分
证明的思路是因为 $n$ 可以做$(m+1)$-互异拆分，那么它的$m$-最大积互异拆分$S$不能含有$2$,且如果 $S$ 包含 $3$, 断点后的元素至少有2个。分情况，引入新元素 $2$, 并对现有的某个元素做相应调整(使元素和不变), 可以证明这个新构造出的$(m+1)$-互异拆分有更大的元素积。而这个拆分的元素积不大于 $m+1-$最大积互异拆分。由此命题得证。

上面是个大体的思路，应该是可以走通的。举例子形象说明意思。

$\{3,4,5,7,8\}\to \{\mathbf{2},3,4,5,7,\mathbf{8-2}\}=\{2,3,4,5,6,7\}$ 显然有 $2\times 6 > 8$
$\{3,4,5,7\}$不可能有 $5$-互异拆分. 很容易证明第$m$个结点是可以做$m$拆分的最小整数。而 $3+4+5+7=19<20$(第$5$结点).
$\{2,3,4,\cdots, i, i+2, \cdots, m+2\}$(中间恰有一个断点) 不可能有$(m+1)$-拆分，理由同上。
从上面的例子已经足够构造出这个命题的完整证明的，我感觉。


命题4‘: 最大积互异拆分是基数最大且最大元素最小(其实只保留后者就可以了，后者implies前者)的互异拆分。这个命题与楼主的算法等价。还是不证，感觉能走通。