数组重排后求所有前缀子数组最小缺失非负整数的最大和

你测试发现的升序排列能得到最大总和的结论是完全正确的。

首先明确Bi的基本性质：对长度为i的前缀Si，Bi是其中没出现的最小非负整数，Bi > k的充要条件是：0到k的所有整数都已经出现在Si里了。
我们的目标是让所有Bi的和最大，换个计数角度理解会简单很多：

算总和的时候不用逐个算每个前缀的Bi值，换个维度计数：Bi的数值等于“有多少个非负整数比Bi小”，比如Bi=3就意味着0、1、2都比它小，对应贡献3。所以总总和等价于「对每个非负整数k，统计有多少个前缀满足Bi > k，再把所有统计值相加」，结果和直接累加Bi完全一致。

那要让总和最大，对每个k来说，就要让满足Bi>k的前缀数量尽可能多。而Bi>k要求0_{k全部出现在前缀里，那最优选择一定是让0}k这些数尽可能早地出现在数组中：

• 要让k=0的贡献最大，就得把0放在数组最开头，这样从第一个前缀开始所有前缀都包含0，0的贡献能达到最大值N；如果0放第2位，第一个前缀没有0，B1=0，0的贡献直接少1。
• 要让k=1的贡献最大，在0已经放最前面的前提下，1要紧跟在0后面放，这样从第二个前缀开始所有前缀都凑齐0和1，1的贡献能达到最大值N-1；如果1放第3位，第二个前缀没有1，B2=1，1的贡献又少1。
• 以此类推，把0、1、2……按从小到大的顺序依次放在数组最靠前的位置，就能让每个k对应的贡献都达到最大值，剩下的重复数字、大于全局mex（整个数组缺失的最小非负整数）的数字随便排在后面就行，不会影响总和。

反过来如果不按升序排，把某个小的数放得靠后，就会拖慢凑齐0~k的速度，直接让对应的k的贡献减少，总和就会变小。你举的N=3的例子里，升序排[0,1,2]刚好让每个k都拿到最大贡献，总和1+2+3=6就是理论最大值，完全符合这个逻辑。

• 第一步：直接对原数组做升序排序，这一步得到的就是能取到最大总和的最优重排数组。
• 第二步：遍历排序后的数组，维护一个标记数组或者集合记录已经出现过的数字，再维护一个变量存当前的mex值，初始为0。每遍历到一个新元素加入当前前缀，就检查：如果当前mex对应的数已经出现过，就把mex加1，直到mex对应的数没出现过为止。
• 第三步：每处理完一个前缀（也就是每遍历完一个元素），就把当前的mex值加到总和里，遍历完整个数组得到的就是最大总和。

举个带重复元素的测试用例验证：比如N=4，原数组为[0,0,2,3]，升序排后是[0,0,2,3]，计算过程：

• i=1，前缀[0]，mex=1，总和加1
• i=2，前缀[0,0]，mex还是1，总和加1
• i=3，前缀[0,0,2]，缺1，mex=1，总和加1
• i=4，前缀[0,0,2,3]，缺1，mex=1，总和加1
  最终总和是4。如果不按升序排，比如把0放到第二位得到[2,0,0,3]，第一个前缀mex是0，后面三个前缀mex是1，总和只有3，确实比升序的结果小。

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