Сегмент дужине k највећег просека - Решење

Поставка

Приметимо да је проблем налажења сегмента дужине \(k\) чији је просек највећи, еквивалентан проблему налажења сегмента дужине \(k\) највећег збира. Просек сегмента добијамо дељењем суме сегмента са дужином сегмента, која је у овом задатку константа и износи \(k\), тако да је просек највећи када је збир највећи.

Груба сила

Задатак решавамо тако што анализирамо све сегменте дужине \(k\), почев од сегмента који почиње од елемента \(a_0\) до сегмента који почиње од елемента \(a_{n-k}\). Одређујемо збир сваког сегмента и уврђујемо који је последњи сегмент максималног збира. Одређивање позиције на којој почиње последњи сегмент максималног збира вршимо уобичајеним алгоритмом одређивања позиције максимума тј. минимума, при чему, пошто се тражи последњи сегмент, индекс максимума ажурирамо када год се наиђе на сегмент који има збир који је већи или једнак тренутном максимума (када би се тражио први сегмент, индекс би се ажурирао само када се наиђе на сегмент који има збир који је строго већи од тренутно максималног).

Директан приступ би био да се рачунање збира елемената сегмента који почиње од елемента \(a_i\) реализује тако што ће се редом сабирати елементи \(a_{j}\) за \(j\) од \(i\) до \(i+k-1\) (применом класичног алгоритма сабирања елемената низа).

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

// pronalazi indeks pocetka segmenta duzine k ciji je prosek najveci
int pocetakSegmentaNajvecegProseka(const vector<double>& a, int k) {
  // duzina niza
  int n = a.size();

  // trenutna maksimalna suma segmenta i indeks njenog pocetka
  double maxSuma = numeric_limits<double>::min();
  int maxPocetak = 0;

  for (int i = 0; i <= n - k; i++) {
    // izracunavamo sumu segmenta duzine k koji pocinje na poziciji i
    double suma = 0;
    for (int j = i; j < i+k; j++)
      suma += a[j];
    // double suma = accumulate(next(a, i), next(a, i+k), 0.0);

    // ako je potrebno, azuriramo maksimum
    if (suma >= maxSuma) {
      maxSuma = suma;
      maxPocetak = i;
    }
  }
  
  // vracamo pocetak poslednjeg segmenta sa maksimalnom sumom
  // (ujedno i prosekom)
  return maxPocetak;
}

int main() {
  ios_base::sync_with_stdio(false);
  
  // ucitavamo podatke
  int n, k;
  cin >> k >> n;
  vector<double> a(n);
  for (int i = 0; i < n; i++)
    cin >> a[i];

  // ispisujemo rezultat
  cout << pocetakSegmentaNajvecegProseka(a, k) << endl;

  return 0;
}

Сложеност. Број операција сабирања у овом алгоритму приступу је око \((n-k)\cdot k\) (јер одређивање сваког од \(n-k\) сегмената захтева око \(k\) операција сабирања), што даје квадратни број операција када је \(k\) око \(n/2\). Временску сложеност најгорег случаја, дакле, можемо проценити са \(O(n^2)\). Пошто све елементе памтимо у низу, меморијска сложеност је \(O(n)\).

Инкременталност - покретни прозор

Међутим, пошто се узастопни сегменти у великој мери преклапају (разликују им се само почетни и завршни елемент) могућ је и бољи приступ, у којем се збир наредног сегмента дужине \(k\) рачуна на основу познатог збира претходног сегмента дужине \(k\). Ако са \(S_i\) обележимо збир сегмента који почиње од елемента \(a_i\) и дужине је \(k\), \(S_i = a_i + a_{i+1} + ... + a_{i+k-1}\), лако се може показати да за \(i > 0\) важи једнакост \(S_i = S_{i-1}- a_{i-1} + a_{i+k-1}\). Према томе можемо израчунати збир \(S_0\) као збир првих \(k\) елемената низа (опет уобичајеним алгоритмом сабирања), а затим за свако \(i\) од \(1\) до \(n-k\) наредни збир \(S_i\) добијамо на основу претходне једнакост. Дакле, ефикасније решење добијамо ако збир рачунамо инкрементално (сваки наредни члан се израчунава на основу претходних).

#include <iostream>
#include <vector>

using namespace std;

// pronalazi indeks pocetka segmenta duzine k ciji je prosek najveci
int pocetakSegmentaNajvecegProseka(const vector<double>& a, int k) {
  // duzina niza
  int n = a.size();
  
  // suma pocetnog segmenta duzine k
  double suma = 0;
  for (int i = 0; i < k; i++)
    suma += a[i];

  // trenutna maksimalna suma segmenta i indeks njenog pocetka
  int maxPocetak = 0;
  double maxSuma = suma;

  for (int i = 1; i <= n - k; i++) {
    // izracunavamo sumu segmenta duzine k koji pocinje na poziciji i
    suma = suma - a[i - 1] + a[i + k - 1];

    // ako je potrebno, azuriramo maksimum
    if (suma >= maxSuma) {
      maxSuma = suma;
      maxPocetak = i;
    }
  }

  // vracamo pocetak poslednjeg segmenta sa maksimalnom sumom
  // (ujedno i prosekom)
  return maxPocetak;
}

int main() {
  ios_base::sync_with_stdio(false);
  
  // ucitavamo podatke
  int n, k;
  cin >> k >> n;
  vector<double> a(n);
  for (int i = 0; i < n; i++)
    cin >> a[i];

  // ispisujemo rezultat
  cout << pocetakSegmentaNajvecegProseka(a, k) << endl;
  return 0;
}

Сложеност. Оптимизовани приступ је знатно ефикаснији у односу на директни, јер се у сваком кораку петље врши само константан број операција, па је сложеност алгоритма линеарна тј. \(O(n)\). Елементи се чувају у низу дужине \(n\), па је меморијска сложеност \(O(n)\).