количество подмассивов со средним значением больше среднего для остальных элементов массива

Question

Нам дан массив размером <2000 </p>

и A [i] <10 ^ 6. Я знаю грубый подход. Можем ли мы лучше, т.е. в линейное время? </p>

IЯ проверяю каждый подмассив и сравниваю его среднее с другими элементами.

Answer 1

public class FindingSubArray {

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);

    int n = in.nextInt();
    int[] arr = new int[n];

    for (int i = 0; i < n; i++) {
        arr[i] = in.nextInt();
    }

    ArrayList<Integer> a = new ArrayList<>();
    ArrayList<Integer> b = new ArrayList<>();

    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            double avg1 = getAverage(i,j,arr);
            double avg2 = getAverageOfRest(i,j,arr);
            //System.out.println(avg1+" "+avg2);
            if(avg1 > avg2) {
                a.add(i+1);
                b.add(j+1);
            }
        }
    }

    System.out.println(a.size());
    for(int i=0;i<a.size();i++){
        System.out.println(a.get(i)+" "+b.get(i));
    }
}

private static double getAverageOfRest(int i, int j, int[] arr) {
    double result = 0;
    int count = 0;

    for(int k=0;k<i;k++) {
        result += arr[k] ;
        count ++;
    }
    for(int k=j+1;k<arr.length;k++) {
        result += arr[k] ;
        count ++;
    }
    if(count > 0)
        return result/count;
    else
        return 0;   
}

private static double getAverage(int i, int j, int[] arr) {
    double result = 0;
    int count = 0;
    for (int k = i; k <= j; k++) {
         result += arr[k] ;
        count ++;
    }

    if(count > 0)
        return result/count;
    else
        return 0;
}

}