一、题目

给你一个整数 finalSum。请你将它拆分成若干个互不相同的正偶数之和，且拆分出来的正偶数数目最多。

比方说，给你 finalSum = 12，那么这些拆分是符合要求的（互不相同的正偶数且和为 finalSum）：(2 + 10) ，(2 + 4 + 6) 和 (4 + 8) 。它们中，(2 + 4 + 6) 包含最多数目的整数。注意finalSum不能拆分成(2 + 2 + 4 + 4)，因为拆分出来的整数必须互不相同。
请你返回一个整数数组，表示将整数拆分成最多数目的正偶数数组。如果没有办法将finalSum进行拆分，请你返回一个空数组。你可以按任意顺序返回这些整数。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-split-of-positive-even-integers

二、思路

2.1 贪心算法

为什么贪心算法要叫这个名字？本来贪心是用来形容欲望大，不知足。这里，贪心是指每一步都贪图当前最优的选择，即局部最优解，而不考虑该选择对后续步骤的影响。
举个非常简单的例子：假设现在有4张钞票：1元、5元、10元和20元，现在允许你每次拿1张，最多拿2张，你会怎么拿才能让自己得到最多的钱？
一年级的小朋友都知道，肯定要从大的面值开始拿，也就是先拿20元，再拿10元。最后就能得到30元巨款。其实这就是贪心算法的核心思想：贪图当前最优。

2.2 确定算法

回到题目，为什么这个题能用贪心算法进行求解？或者往大了说，我们什么时候应该想到使用贪心算法进行求解？
对于贪心算法，我们需要知道一点：不保证最优解，什么意思？大白话说就是可能得到的答案是错误的！所以在应用贪心算法之前，我们要仔细分析问题，并判断是否适合使用贪心算法。
一般来说，如果题目满足下面的条件，我们可以选取贪心算法求解：
1. 问题具有贪心选择性质：通过局部最优的选择达到全局最优，也就是说最优解不需要进行全局考虑。
2. 问题的子问题相互独立：当前的选择不会影响后续的选择。
来看本题目：
1. 要拆分 finalSum，并取得最大的拆分数目，并且拆分出来的偶数互不相同。我们希望拆分成尽可能多的偶数，所以应该尽可能拆份成最小的若干个偶数。这样就满足了问题具有贪心选择性质的特点。
2. 当前的选择也并不会影响之后的选择，满足了问题的子问题相互独立的特点。所以自然而然，我们想到了使用贪心算法进行求解。

三、详细算法

3.1 算法分析

前面分析了为什么要使用贪心算法，接下来看一下具体的实现步骤。
1. 从最小的偶整数2开始依次尝试拆分，直到剩余的数值小于等于当前被拆分的最大偶整数为止。此时，我们已经拆分成尽可能多的偶数，不可能拆分出更多的互不相同的偶数。
2. 如果此时拆分后剩余的 finalSum 大于零，则将这个数值加到最大的偶整数上，从而保证所有的数互不相同。
还是举个例子可能会更清楚一点。比如拿32来拆分。
1. 取 2，此时 finalSum = 30 ans = [2]
2. 取 4，此时 finalSum = 26 ans = [2,4]
3. 取 6，此时 finalSum = 20 ans = [2,4,6]
4. 取 8，此时 finalSum = 12 ans = [2,4,6,8]
5. 取 10，此时 finalSum = 2 ans = [2,4,6,8,10]
6. 这时，能取的最小偶数已经比剩下的数还大了(10 > 2)，自然已经无法进行拆分了，最后将剩下的2加在当前的最大值10上面，这样可以保证结果不重复。
7. 最终我们得到了正确结果(之一)：[2,4,6,8,12]

3.2 详细题解

class Solution {
    public List<Long> maximumEvenSplit(long finalSum) {
        //结果集合，用来保存最终结果
        List<Long> ans = new ArrayList<>();
        //如果不是偶数，不能被拆分，返回空集合
        if (finalSum % 2 != 0) {
            return ans;
        }
        //开始遍历，每次将 i 加2
        for(long i = 2;i <= finalSum;i += 2){
            //将 i 放入结果集合。即按照 2，4，6...的顺序添加进集合
            ans.add(i);
            //finalSum 减去 i
            finalSum -= i;
            //如果遇到剩下的数比 i 还小了，说明分不下去了，将最后一个数加在 ans 倒数的第二个数上面，以免重复
            //比如 28 的拆分过程：i = 2，4，6，8   finalSum = 26，22，16，8   此时 i >= finalSum（8） 了，将 8 加到上一个结果中
            //最终结果变为：2，4，6，8 + 8  即 2，4，6，16
            if(i >= finalSum){
                //由于前面已经将 i 放入了集合，主要更改最后放入的值
                ans.set(ans.size() - 1,finalSum += ans.get(ans.size() - 1));
                break;
            }
        }
        return ans;
    }
}