Поглед на реку - Решење

Задатак захтева да се за сваку позицију \(i\) у низу одреди максимум свих елемената од те позиције па до краја низа (тј. да се одреди \(m_i = \max(a_i, \ldots, a_{n-1})\)).

Приметимо да се овде захтева рачунање максимума серије суфикса низа, што је заправо веома слично израчунавању максимума серије префикса низа. Израчунавање серије максимума префикса низа описано је у задатку Најбољи “сабмит”.

Груба сила

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

Инкременталност

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

Задатак решавамо тако што у петљи пролазимо кроз низ у обрнутом редоследу, крећући се од последњег члана низа (који је индексиран са \(n-1\)) до првог члана (који је индексиран са 0). Максимум иницијализујемо на нулу. У сваком пролазу кроз петљу, анализира се вредност текућег елемента низа који се пореди са текућим максимумом. Ако је вредност текућег елемента низа већа од текућег максимума (који у ствари представља максималану вредност елемената десно од текућег), нови текући максимум постаје баш тај члан низа. Један проблем са овим решењем је што се максимуми одређују у супротном редоследу од оног који је потребно исписати. Зато је пре исписа потребно упамтити их. Једно решење би било да се они памте у новом низу. Ако не желимо да ангажујемо додатну меморију, можемо приметити да се након одређивања максимума \(m_i\) елемент \(a_i\) неће више анализирати, па се \(m_i\) може уписати на место елемента \(a_i\). На крају, исписаћемо елементе низа у који смо сместили максимуме од почетка.

#include <iostream>
#include <vector>

using namespace std;

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

  // maksimalni element od pozicije i do kraja niza
  int max = 0;
  for (int i = n - 1; i >= 0; i--) {
    // ako je tekuci element veci od maksimalnog iza njega, onda je
    // potrebno azurirati maksimum
    if (a[i] > max)
      max = a[i];
    // belezimo vrednost maksimuma (koristimo slobodno prostor niza a,
    // jer nam vrednost a[i] vise nece biti potrebna)
    a[i] = max;
  }

  // ispisujemo rezultat
  for (int i = 0; i < n; i++)
    cout << a[i] << endl;

  return 0;
}