Максимални збир сегмента - Решење

Збирови префикса

Један алгоритам којим можемо ефикасно решити овај задатак се заснива на коришћењу збирова префикса. Сличну техника је описана, на пример, у задатку Збирови сегмената. Ако знамо збир сваког префикса низа, онда збир сваког сегмента можемо добити као разлику збирова два префикса. Збир елемената сегмента \([l, d]\) једнак је разлици збира елемената сегмента \([0, d+1)\) и збира елемената сегмента \([0, l)\), тј. важи да је

\[\sum_{i=l}^d a_i = \sum_{i=0}^{d} a_i - \sum_{i=0}^{l-1}a_i\]

Рачунамо да је збир празног сегмента \([0, 0)\) по дефиницији једнак нули.

За сваку позицију у низу одређујемо максимални збир суфикса који се на тој позицији завршава. Највећи од свих максималних збирова суфикса је највећи збир неког сегмента у низу (јер је сваки сегмент заправо суфикс дела низа до оне позиције на којој се тај сегмент завршава).

Користимо индуктивноу конструкцију и низ проширујемо једним по једним елементом. Крећемо од празног низа чији је максимални збир сегмента једнак нули. Приликом сваког проширивања низа новим елементом, претпостављамо да знамо максимум збирова сегмента у непроширеном делу низа и да израчунамо максимални збир суфикса проширеног низа. Максимум збирова сегмента у проширеном низу је већи од та два броја.

Максимални збир суфикса проширеног низа, на основу разлагања на збирове префикса, добија се као разлика збира целог проширеног низа (тј. збира префикса до текуће позиције) и збира неког префикса непроширеног низа (празан суфикс не морамо анализирати, јер је празан сегмент већ обрађен у склопу иницијализације). Пошто је умањеник константан, да бисмо максимизовали разлику потребно да знамо најмањи могући умањилац, тј. да знамо најмањи збир префикса који се завршава на некој позицији испред текуће. И текући и минимални збир префикса можемо одржавати инкрементално. Инкрементално израчунавање збирова префикса већ је описано у задатку Највећи збир префикса.

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

Приметимо да је у овом решењу је индуктивна хипотеза појачана и претпостављамо да поред сегмента највећег збира у обрађеном делу низа умемо да одредимо и минимални збир префикса обрађеног дела низа.

#include <iostream>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  int n;
  cin >> n;
  
  int zbir_prefiksa = 0;
  int min_zbir_prefiksa = zbir_prefiksa;
  int max = 0;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    zbir_prefiksa += x;
    int zbir_segmenta = zbir_prefiksa - min_zbir_prefiksa;
    if (zbir_segmenta > max)
      max = zbir_segmenta;
    if (zbir_prefiksa < min_zbir_prefiksa)
      min_zbir_prefiksa = zbir_prefiksa;
  }
  cout << max << endl;
  
  return 0;
}