Ищем в массиве подмассив нужной длины с максимальным средним значением
В отличие от предыдущей заметки, ищем в целочисленном массиве подмассив фиксированной длины 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; }
21.02.2019, 14:06 [1442 просмотра]