Најбољи “сабмит” - Решење

Поставка

За сваку позицију \(i\) у серији бројева је потребно одредити највећи међу свим бројевима од почетка серије, закључно са тренутним елементом \(m_i = \max{(a_0, \ldots, a_i)}\).

Груба сила

Наивни начин да се то уради је да се резултати свих слања упишу у низ, а затим да се за сваку позицију \(i\) од \(0\) до \(n-1\) одреди и испише максимум \(m_i\). Одређивање максимума се може урадити уобичајеним алгоритмом одређивања максимума серије бројева.

Сложеност. Ово решење је прилично неефикасно (има квадратну сложеност у односу на број слања, тј. сложеност \(O(n^2)\)).

#include <iostream>
#include <vector>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<int> poeni(n);
  for (int i = 0; i < n; i++)
    cin >> poeni[i];

  for (int i = 0; i < n; i++) {
    int maxPoena = poeni[0];
    for (int j = 1; j <= i; j++)
      if (poeni[j] > maxPoena)
        maxPoena = poeni[j];

    cout << maxPoena << endl;
  }
  return 0;
}

Библиотечке функције - скривена сложеност

Максимум дела низа можемо одредити и библиотечком функцијом. У језику C++ можемо употребити функцију max_element.

Сложеност. Иако сада програм има само једну петљу, у функцији за израчунавање максимума је скривена линеарна сложеност, па укупна је сложеност \(O(n^2)\).

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<int> poeni(n);
  for (int i = 0; i < n; i++)
    cin >> poeni[i];

  for (auto it = next(begin(poeni)); it <= end(poeni); it++)
    cout << *max_element(begin(poeni), it) << endl;

  return 0;
}

Инкременталност серије парцијалних максимума

Кључни увид којим се може доћи до ефикаснијег решења је да се приликом додавања новог елемента максимум проширене серије \(m_{i+1}\) може израчунати крајње једноставно ако је познат максимум \(m_i\) серије пре проширења. Наиме, ако је познат број поена такмичара пре текућег слања задатка, када се одреди број поена у том слању, максимум се или увећава (ако је у текућем слању остварен највећи број поена до тада) или се не мења тј. \(m_{i+1} = \max(m_i, a_{i+1})\). Почетни максимум може бити постављен или на први елемент низа (важи да је \(m_0 = a_0\)), или, пошто су сви елементи ненегативни, на нулу (важи да је \(m_{-1} = 0\)). Дакле, принцип инкременталности који важи за парцијалне збирове, важи и за парцијалне максимуме. Инкрементално израчунавање серије парцијалних збирова (збирова префикса) описано је, на пример, у задатку Највећи збир префикса.

Дакле, у задатку се примењује класичан алгоритам одређивања максимума серије бројева, али се у сваком кораку исписује текућа вредност максимума.

Сложеност. Иницијализација се врши у времену \(O(1)\) и сваки нови максимум се од претходног добија у времену \(O(1)\), па се \(n\) максимума израчунава у укупном времену \(O(n)\). Ово решење не учитава истовремено све елементе у низ, па је меморијска сложеност \(O(1)\). Са друге стране у овом решењу се наизменично учитавају и исписују бројеви, што у језику C++ захтева да се библиотека за улаз и излаз посебно подеси, да би се искључило стално пражњење бафера, које успорава програм (довољно је навести cin.tie(0) и уместо endl користити '\n'. 

#include <iostream>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n;
  int maxPoena = 0;
  for (int i = 0; i < n; i++) {
    int poeni;
    cin >> poeni;
    if (poeni > maxPoena)
      maxPoena = poeni;
    cout << maxPoena << '\n';
  }
  return 0;
}