算法:给定一个数组，找出重排后的最大和

Question

给定一个数组A，大小为N，包含0-N之间的数字。对于从第0个索引开始的每个子数组，比如Si，我们说Bi是Si中不存在的最小的非负数。

我们需要找到这个数组中所有Bi的最大可能和

我们可以重新排列数组以获得最大的和。

例如:

A = 1,2,0, N = 3

那么我们把它重新排列成A= 0,1,2

S1 = 0, B1= 1

S2 = 0,1 B2= 2

3= 0,1,2, 3

所以和是6

无论我尝试过什么例子，我都看到排序数组将给出最大的和。我是对的还是遗漏了什么?

请帮忙找出这个问题的正确逻辑。我不是在寻找最佳解决方案，而是在寻找正确的逻辑。

Answer 1

是的，对数组进行排序会使变量变量的和最大化。由于输入大小为𝑛，因此它不包括{0，…，𝑛}，因为这是一组𝑛+ 1的数字。假设它只缺少值𝑘，那么对于所有的离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别离别如果有其他数缺失，但大于𝑘，则对任意一个变量变量_变量没有影响。

因此我们需要找出{0，…范围内的最小缺失值𝑘,𝑛}。然后最大值是1 + 2 +…+𝑘+(𝑛−𝑘)𝑘。这是𝑘(𝑘+ 1)/2 +(𝑛−𝑘)𝑘=𝑘(1 + 2𝑛−𝑘)/2

要查找𝑘的值，创建一个大小为𝑛+ 1的布尔数组，并在输入中遇到𝑣时将索引𝑣处的条目设置为true。𝑘则是该布尔数组仍然为假值的第一个索引。

下面是一个JavaScript代码片段:

function maxSum(arr) {
const n = arr.length;
const isUsed = Array(n + 1).fill(false);
for (const value of arr) {
isUsed[value] = true;
}
const k = isUsed.indexOf(false);
return k * (1 + 2*n - k) / 2;
}
console.log(maxSum([0, 1, 2])); // 6
console.log(maxSum([0, 2, 2])); // 3
console.log(maxSum([1, 0, 1])); // 5