打印数组 A 的最大可能商

Question

给定一个包含 N 个整数的数组 A。你的老师要求你找出数组的最大商。大小为 N 的数组 A 的商可以通过以下方式计算：

1. 设数组A的N个元素之和为X。

2. 令 pre[] 为另一个大小为 N 的数组，其中对于每个索引 i (1 <= i <= N), prei gives us the sum of elements A1 + A2 +. . + Ai.

3. 数组 A 的商将等于 X/prei 的下取整值对从 1 到 N 的每个 i 值的总和。

您可以交换数组 A 的任意两个元素。找到数组 A 的最大可能商。

输入

输入的第一行包含一个整数 N。

第二行包含N个空格分隔的整数Ai

限制：

1 <= N <= 10^5

1 <= Ai <= 10^8

输出

打印数组 A 的最大可能商。

示例

示例输入：

3

1 1 3

示例输出：

8

说明：

数组 pre[] = [1, 2, 5]

数组 A 的总和 X = 5

数组 A 的商 = 5/1 + 5/2 + 5/5 = 5 + 2 + 1 = 8

可以证明它们不可能比数组A更大的商

var furthest = function(n, arr) {
  // Sort the array in non-decreasing order
 arr.sort((a, b) =\> a - b);

// Calculate prefix sum array
    let pre = new Array(n).fill(0);
    pre[0] = arr[0];
    for (let i = 1; i < n; i++) {
        pre[i] = pre[i - 1] + arr[i];
    }

// Calculate maximum quotient
    let maxQuotient = 0;
    for (let i = 0; i < n; i++) {
        let quotient = pre[i] * (i + 1) + (pre[n - 1] - pre[i]);
        maxQuotient = Math.max(maxQuotient, quotient);
    }

    return maxQuotient;

};

代码错误的地方是输出 15 而不是 8 ？

Answer 1

我认为排序后的数组足以计算最大商。

var furthest = function(n, arr) {
  // Sort the array in non-decreasing order
 arr.sort((a, b) => a - b);

// Calculate prefix sum array
    let pre = new Array(n).fill(0);
    pre[0] = arr[0];
    for (let i = 1; i < n; i++) {
        pre[i] = pre[i - 1] + arr[i];
    }
    let X = pre[n-1]

// Calculate maximum quotient
    let maxQuotient = 0;
    for (let i = 0; i < n; i++) {
        maxQuotient += parseInt(X/pre[i])
    }

    return maxQuotient;

};