БлогNot. Ищем в массиве подмассив нужной длины с максимальным средним значением

Ищем в массиве подмассив нужной длины с максимальным средним значением

В отличие от предыдущей заметки, ищем в целочисленном массиве подмассив фиксированной длины k с максимальным средним значением.

Но вычислять все средние подряд тоже не нужно, а лучше создать вспомогательный массив csum размерностью n, i-ый элемент которого csum[i] будет содержать сумму элементов от arr[0] до arr[i]. Если у нас есть массив csum, мы сможем вычислять сумму значений между двумя индексами за время O(1). Если ответов несколько, будет найден первый из них.

Ниже приводится листинг консольной программки, которая запускалась в Visual Studio 2015.

#include <iostream> 
using namespace std;

int findMaxAverage(int arr[], int n, int k) {
 if (k > n) return -1;
 int *csum = new int[n];
 csum[0] = arr[0];
 for (int i = 1; i<n; i++) csum[i] = csum[i - 1] + arr[i];
 int max_sum = csum[k - 1], max_end = k - 1;
 for (int i = k; i < n; i++) {
  int curr_sum = csum[i] - csum[i - k];
  if (curr_sum > max_sum) {
   max_sum = curr_sum;
   max_end = i;
  }
 }
 delete[] csum;
 return max_end - k + 1;
}

int main() {
 int arr[] = { 1, 2, 3, 4, 5, 4, 3, 2, 1 };
 int k = 4;
 int n = sizeof(arr) / sizeof(arr[0]);
 int start = findMaxAverage(arr, n, k);
 for (int i = start; i<start + k; i++) cout << arr[i] << " ";
 cout << endl << k << " item(s)";
 cin.get();
 return 0;
}

теги: алгоритм c++

21.02.2019, 14:06; рейтинг: 485