数组拆分

记住「排序后取偶数下标之和」这套口诀，下面每一帧都在套它。

这是原始乱序数组 [13,6,1,28,5,17,4,9]。贪心的第一步是排序，先把它从小到大理顺，之后相邻的数才能正好配成一对。

第 1 轮：在还没排序的那段里挑出最小的 1，放到下标 0（绿色）。它左边的蓝色部分都已经从小到大排好了。

第 2 轮：在还没排序的那段里挑出最小的 4，放到下标 1（绿色）。它左边的蓝色部分都已经从小到大排好了。

第 3 轮：在还没排序的那段里挑出最小的 5，放到下标 2（绿色）。它左边的蓝色部分都已经从小到大排好了。

第 4 轮：在还没排序的那段里挑出最小的 6，放到下标 3（绿色）。它左边的蓝色部分都已经从小到大排好了。

第 5 轮：在还没排序的那段里挑出最小的 9，放到下标 4（绿色）。它左边的蓝色部分都已经从小到大排好了。

第 6 轮：在还没排序的那段里挑出最小的 13，放到下标 5（绿色）。它左边的蓝色部分都已经从小到大排好了。

第 7 轮：在还没排序的那段里挑出最小的 17，放到下标 6（绿色）。它左边的蓝色部分都已经从小到大排好了。

排序完成，现在数组是 [1,4,5,6,9,13,17,28]，从左到右一个不大于下一个。接下来按相邻两个一对来配。

先体会贪心的核心：最大的 28 不管和谁配，它都是那一对里较大的，永远拿不到。既然它一定被舍弃，就让它去和紧挨着的次大 17 配对，这样次大的 17 就能被保留成较小值。排序正是为此服务。

排好序后，从左到右相邻两个配成一对。每一对里左边的数一定不大于右边，所以较小值就是左边、也就是偶数下标的那个。下面逐对来取。

看第 1 对：1 和 4。排过序，左边的 1 不会比右边的 4 大，所以这一对的较小值就是 1。

把较小的 1 收进答案（变绿），右边较大的 4 注定当不了较小值，灰掉舍弃。现在 ans 累计到 1。

看第 2 对：5 和 6。排过序，左边的 5 不会比右边的 6 大，所以这一对的较小值就是 5。

把较小的 5 收进答案（变绿），右边较大的 6 注定当不了较小值，灰掉舍弃。现在 ans 累计到 6。

看第 3 对：9 和 13。排过序，左边的 9 不会比右边的 13 大，所以这一对的较小值就是 9。

把较小的 9 收进答案（变绿），右边较大的 13 注定当不了较小值，灰掉舍弃。现在 ans 累计到 15。

看第 4 对：17 和 28。排过序，左边的 17 不会比右边的 28 大，所以这一对的较小值就是 17。

把较小的 17 收进答案（变绿），右边较大的 28 注定当不了较小值，灰掉舍弃。现在 ans 累计到 32。

四对都取完了，绿色这四个偶数位 1、5、9、17 加起来正好 32，这就是最大总和。灰色那几个大数在各自的对里都被舍弃了。

边界先想清：只有一对、全相等、含负数，规则都不变。

面试重点：会用交换论证说清贪心为什么对。