findMaxAverage с большим массивом неудачных тестов

Question

Q: Дано n целых чисел, найти непрерывный подмассив с наибольшим средним и длиной k и вывести максимальное среднее.

input: [1,12, -5, -6,50,3],k = 4
выход: 12,75
например: maxAvr (12-5-6 + 50) / 4 = 51/4 = 12,75

---

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        double[] f = new double[nums.length];//save the max value f[i] with range k from nums[]
        int length = nums.length;
        int sum = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        if (length == k) {
            return ((double) sum /  k);
        }
        f[k - 1] = (double)sum; // start at f[k-1]
        for (int i = k - 1; i < length - 1; i++) {
            f[i + 1] = f[i] - nums[i - k + 1] + nums[i + 1]; // with dp to find the maxValue in the range k 
        }
        Arrays.sort(f);
        return (double) f[length - 1] / (double) k;
    }
}

---

Отладка

• rong Неверный ответ
• ✘ контрольный пример: большой массив с 6514 элементами
• passed 118/123 пропущенных дел (нет данных)
• ✘ Ответ:
• ✘ Stdout: '0.0'

Когда я отлаживаю, я нахожу idea.sh не может решить большой массив

Answer 1

Спасибо, я решил, Arrays.sort () тратит много времени, поэтому я использую другой метод!

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        double[] f = new double[nums.length];
        int length = nums.length;
        int sum = 0;
        double pre = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        if (length == k) {
            return ((double) sum /  k);
        }
        f[k - 1] = (double)sum; 
        pre = f[k-1]; // save the max  value
        for (int i = k - 1; i < length -1; i++) {
            f[i + 1] = f[i] - nums[i - k + 1] + nums[i + 1]; 
            if(f[i+1]>pre){
                pre = f[i+1]; // exchange the max value 
            }
        }
        // Arrays.sort(f);   // waste much time!
        return (double) pre / (double) k;
}
}