2178. 拆分成最多数目的正偶数之和 (opens new window)

1.贪心

分析：深搜复杂度太高肯定超时。这里题目给的例子有一定的干扰作用：28->[6,8,2,12]，实际上也可以分解成[2,4,6,16]。大胆猜测结果集添加规则如下：

• 每次从小添加连续的相邻偶数
• 如果最后一个偶数添加后超出目标和finalSum，那么当前剩余的部分val=finalSum-sum则加到当前结果集最后一个元素上

完备性证明：

1. 因为是从小到大依次放入相邻偶数，如果当前sum=finalSum，也就是下一个相邻偶数添加后，当前和sum正好等于目标和，那么当前结果集肯定是最优解。

2. 如果存在差额部分val=finalSum-sum，假设当前结果集[2,4,6,8,...k,...m]，那么显然val<=m，按照上述规则最终返回的一个结果集为[2,4,6,8,...k,...m+val]。可以看出val的合并并没有增加结果集的长度。

   而这个val是否有可能与原结果集的某个数k合并后分裂成两个新的偶数 val+k=i + J，这两个偶数i，j满足集合不重复规则可以添加到原结果集中[2,4,6,8,...k-2,k+2...m, i , j ]？这样的话得到集合的元素数目就是最多的。

3. 事实上答案是不可能的。也就是说无论val这部分值怎么操作，都不会增加集合的长度，最大长度就是m/2。证明如下：

   • 记merge=val+k，考虑将merge拆分成merge=a +(merge-a)。
     • 假设a属于[2,4...m]，那么得到的两个元素是无效的，因为a已经存在原结果集中。
     • 而如果a和merge-a都是不重复的大于m的偶数，虽然满足不重复条件可以加入结果集，但因为val<=m，val+k<2m。因此这样的两个偶数肯定分不出来。
   • 综上，val和原结果集的任何一个数合并后，都不能再分成另外两个大于m的偶数。

class Solution {
    public List<Long> maximumEvenSplit(long finalSum) {
        List<Long> res=new ArrayList<>();
        if(finalSum%2==1) return res;
        long sum=0;
        for(long i=2;;i+=2){
            sum+=i;
            res.add(i);
            if(sum+i+2>finalSum) break;
        }
        long val=finalSum-sum;
        long tail=res.remove(res.size()-1)+val;
        res.add(tail);
        return res;
    }
}