Найти в массиве целых чисел подмассив максимальной длины с максимальным средним значением

Странная задачка, для которой никакого среднего искать, вроде бы, и не нужно.

Соображения такие:

• среднее от любого подмассива не может превышать значения максимального элемента;
• искомый подмассив будет содержать максимальный элемент массива;
• чтобы найти подмассив максимальной длины с максимальным средним значением, ищем максимальную длину подмассива, каждый элемент которого одинаков и совпадает с максимальноым элементом массива.

Получается временная сложность порядка O(2*n). Консольная программа из Studio 2015 показана ниже.

#include <iostream> 
using namespace std;

int maxSubArray(int a[], int n, int &start) {
 int count, j;
 int cnt = 1, max = a[0];
 for (int i = 1; i < n; i++) {
  if (a[i] > max) { max = a[i]; start = i; }
 }
 for (int i = 0; i < n - 1;) {
  count = 1;
  if (a[i] == a[i + 1] && a[i] == max) {
   for (j = i + 1; j < n; j++) {
    if (a[j] == max) {
     count++; i++;
    }
    else break;
   }
   if (count > cnt) { cnt = count; start = j - cnt; }
  }
  else i++;
 }
 return cnt;
}

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

21.02.2019, 13:54 [1805 просмотров]