Количество подмассивов с X как наиболее часто встречающимся элементом для каждого значения X от 1 до N

Учитывая массив arr[] размера N ( где 0<A[i]<=N для всех 0<=i<N ), задача состоит в том, чтобы вычислить для каждого числа X от 1 до N количество подмассивов в котором X является наиболее часто встречающимся элементом. В подмассивах, где более чем один элемент имеет максимальную частоту, наименьший элемент следует рассматривать как наиболее частый.

Примеры:

Input: arr[]={2, 1, 2, 3}, N=4
Output:
4 5 1 0
Explanation:

1. For X=1, the subarrays where X is the most frequent element, are {2, 1}, {1}, {1, 2}, {1, 2, 3}
2. For X=2, the subarrays where X is the most frequent element, are {2}, {2, 1, 2}, {2, 1, 2, 3}, {2}, {2, 3}
3. For X=3, the subarray where X is the most frequent element, is {3}
4. For X=4, there are no subarrays containing 4.

Input: arr[]={3, 1, 5, 1, 3}, N=5
Output:
12 0 2 0 1

Подход: подход заключается в отслеживании наиболее часто встречающихся элементов в каждом подмассиве с помощью двух циклов и сохранении их в отдельном массиве. Выполните следующие шаги, чтобы решить проблему:

1. Инициализируйте массив размером N до 0 , чтобы сохранить окончательные ответы.
2. Итерируйте от 0 до N-1 и для каждого текущего индекса i сделайте следующее:
   1. Инициализируйте счетчик массива частот размером N до 0 , чтобы сохранить текущие частоты каждого элемента от 1 до N .
   2. Инициализируйте переменную best равным 0 , чтобы сохранить наиболее часто встречающийся элемент в текущем подмассиве.
   3. Итерируйте от i до N-1 и для каждого текущего индекса j сделайте следующее:
      1. Увеличьте количество текущего элемента, т.е. count[arr[j]-1]=count[arr[j]-1]+1
      2. Проверьте, превышает ли частота текущего элемента, т.е. arr[j] , частоту наилучшего.
      3. Проверьте, равна ли частота текущего элемента, т.е. arr[j] , частоте наилучшего , а текущий элемент меньше наилучшего .
      4. Если любой из них истинен, обновить best до текущего элемента, т.е. best=arr[j]
      5. Увеличьте лучший индекс массива ans , т.е. ans[best-1]=ans[best-1]+1 .
3. Распечатайте массив и .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N ² )
Вспомогательное пространство: O(N)