Највећи збир префикса - Решење

Поставка

Засебно израчунавање сваког салда

Под претпоставком да су подаци о свим трансакцијама учитане у низ, директно, наивно решење овог задатка би било да се за сваки дан \(k\) (од \(0\) до \(n-1\)) одреди збир \(Z_k\) елемената од првог дана закључно са даном \(k\) (алгоритмом сабирања серије бројева) и да се онда одреди највећи од тих збирова (алгоритмом одређивања минимума тј. максимума описаним).

#include <iostream>
#include <vector>

using namespace std;

int najveciZbirPrefiksa(const vector<int>& a) {
  // prvog dana je zbir 0
  // najveci zbir prefiksa
  int maxZbir = 0;
  for (int i = 0; i < a.size(); i++) {
    // racunamo zbir prefiksa od pocetka do pozicije i (ukljucujuci i nju)
    int zbir = 0;
    for (int j = 0; j <= i; j++)
      zbir += a[j];
    // azuriramo maksimum ako je potrebno
    if (zbir >= maxZbir)
      maxZbir = zbir;
  }
  return maxZbir;
}

int main() {
  // ubrzavamo ucitavanje
  ios_base::sync_with_stdio(false);
  // ucitavamo sve elemente u niz
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++)
    cin >> a[i];
  // izracunavamo i ispisujemo maksimalni zbir prefiksa
  cout << najveciZbirPrefiksa(a) << endl;
  return 0;
}

Сложеност. Пошто се збир префикса дужине \(k\) може израчунати у \(k\) корака, укупно бисмо извршавали око \(1 + 2 + \ldots + n = \frac{n(n+1)}{2}\) сабирања (и линеарни број ажурирања максимума) и временска сложеност овог наивног алгоритма била би квадратна у односу на број елемената низа тј. \(O(n^2)\).

Скривена сложеност

За сабирање је могуће употребити и библиотечку функцију. У језику C++ то је функција accumulate која сабира све елементе у делу низа ограниченом са два итератора, при чему се вредност збира у почетку иницијализује на вредност прослеђену као трећи параметар те функције. 

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

using namespace std;

int najveciZbirPrefiksa(const vector<int>& a) {
  // prvog dana je zbir 0
  // najveci zbir prefiksa
  int maxZbir = 0;
  // analiziramo iterator iza svake pozicije u nizu
  for (auto it = next(begin(a)); it <= end(a); it++)
    // racunamo zbir prefiksa od pocetka do ispred pozicije it
    // i azuriramo maksimum ako je potrebno
    maxZbir = max(maxZbir, accumulate(begin(a), it, 0));
  return maxZbir;
}

int main() {
  // ubrzavamo ucitavanje
  ios_base::sync_with_stdio(false);
  // ucitavamo sve elemente u niz
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++)
    cin >> a[i];
  // izracunavamo i ispisujemo maksimalni zbir prefiksa
  cout << najveciZbirPrefiksa(a) << endl;
  return 0;
}

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

Скривена сложеност у задацима овог типа је нарочито чест проблем у језицима у којима се збир дела низа израчунава јако једноставно и елегантно. На пример, у језику Python:

maxZbir = 0
for i in range(n):
    maxZbir = max(maxZbir, sum(a[0:i+1]))

Инкрементално израчунавање салда

Много ефикасније решење се може добити ако се примети прилично очигледна чињеница да се салдо у следећем дану може јако једноставно израчунати ако је познат салдо у претходном дану тако што се тај салдо увећа за износ трансакције у следећем дану, што омогућава инкременталност израчунавања. Збир (текући салдо) израчунавамо индуктивном конструкцијом. Означимо са \(Z_k\) збир трансакција у првих \(k\) дана. Важи да је \(Z_0 = 0\) и да је \(Z_{k+1} = Z_k + a_{k}\). Збир зато иницијализујемо на нулу, а онда у петљи учитавамо трансакцију по трансакцију, увећавамо тренутни збир за износ трансакције, проверавамо да ли је текући износ већи од до тада највећег и ако јесте, ажурирамо вредност највећег износа.

#include <iostream>

using namespace std;

int main() {
  // ubrzavamo ucitavanje
  ios_base::sync_with_stdio(false);
  // ucitavamo broj elemenata niza
  int n;
  cin >> n;

  // prvog dana je saldo 0
  // najveci zbir prefiksa
  int maxZbir = 0;
  // tekuci zbir prefiksa
  int zbir = 0;
  for (int i = 0; i < n; i++) {
    // ucitavamo tekuci element niza
    int x; cin >> x;
    // azuriramo zbir prefiksa
    zbir += x;
    // azuriramo maksimum ako je potrebno
    if (zbir >= maxZbir)
      maxZbir = zbir;
  }

  // ispisujemo resenje
  cout << maxZbir << endl;
  return 0;
}

Сложеност. У сваком кораку петље вршимо константан број додатних операција (ажурирање збира и минимума) и сложеност овог алгоритма је линеарна тј. \(O(n)\). Приметимо и да је меморијска сложеност овог решења \(O(1)\), јер током инкременталне обраде нема потребе памтити вредности свих трансакција у низу.