Решење до којег се најједноставније долази је да се масе свих предмета учитају у низ, да се након тога пронађе позиција највећег елемента у низу и да се затим одреди збир елемената низа пре те позиције и збир елемената низа после те позиције.
Задатак можемо решити и без коришћења низова. У овом решењу задатка ћемо комбиновати алгоритам одређивања максимума серије бројева и алгоритам сабирања серије учитаних бројева. У петљи ћемо учитавати једну по једну масу предмета, одржавајући при том збир маса пре прве појаве максималне масе, збир маса после прве појаве максималне масе и саму вредност максималне масе предмета.
На почетку учитавамо масу првог предмета (он постоји по условима задатка), максимум иницијализујемо на ту учитану вредност, а два збира на нулу (јер није виђен ни један предмет ни пре, ни после тог првог предмета који је уједно и прво појављивање до тада максималне масе).
Затим, у петљи учитавамо остале предмете, један по један. Могућа су два случаја.
Ако је маса учитаног предмета строго већа од до тада максималне масе, онда тај предмет представља прво појављивање предмета максималне масе (он је максимални од свих до тада виђених). Зато је потребно да израчунамо збир маса свих предмета пре њега. Међутим, ми знамо вредност збира маса свих предмета пре ранијег предмета максималне масе, знамо његову масу и знамо збир маса предмета након њега (у тај збир још није укључен текући предмет), тако да је збир предмета пре текућег предмета (новог максимума) једнак збиру ове три вредности. Максимум се ажурира на масу текућег предмета, а збир маса предмета после новог максимума се ажурира на нулу (јер за сада нисмо видели ни један такав предмет).
У супротном, текући предмет не представља прво појављивање максимума (он је или мањи од максимума, или је једнак максимуму, али није његово прво појављивање). Зато се предмет максимум не мења, не мења се серија предмета пре њега, док се серија предмета након њега продужава текућим предметом. Зато је у овом случају само потребно ажурирати збир маса предмета после максимума тако што се тај збир увећа за масу текућег предмета.
Доказ коректности. Докажимо формално коректност овог алгоритма. Инваријанту петље чине следећи услови:
max садржи вредност максимума првих \(i\) елемената низа (елемената \(a_0, \ldots, a_{i-1}\)). Претпостављамо да се прво појављивање те вредности јавља на некој позицији \(m\) између \(0\) и \(i-1\) тј. да су сви елементи \(a_0, \ldots, a_{m-1}\) строго мањи од вредности променљиве max, да \(a_m\) има вредност max, а да сви елементи \(a_{m+1}, \ldots, a_{i-1}\) имају вредност већу или једнаку од променљиве max.zbirPreMax садржи збир свих елемената пре првог појављивања максималног елемента max тј. вредност \(a_0 + \ldots + a_{m-1}\).zbirPosleMax садржи збир свих елемената после првог појављивања максималног елемента max тј. вредност \(a_{m+1} + \ldots + a_{i-1}\).Докажимо да су услови заиста инваријанта петље.
Пре уласка у петљу, променљива max има вредност \(a_0\), променљиве zbirPreMax и zbirPosleMax имају вредност \(0\), а променљива i вредност \(1\). Тада је \(m=0\), па су сви услови испуњени (скупови елемената \(a_0, \ldots, a_{m-1}\) и \(a_{m+1}, \ldots, a_{i-1}\) су празни).
Претпоставимо да услови важе пре уласка у петљу.
Претпоставимо да је \(a_i\) строго веће од вредности max. Тада на основу инваријанте знамо да је \(a_i\) строго веће од свих вредности \(a_0, \ldots, a_{i-1}\), па се нова вредност максимума јавља на позицији \(m' = i\).
Тада је нова вредност променљиве zbirPreMax једнака збиру старих вредности променљивих zbirPreMax, zbirPosleMax и max, па на основу инваријанте важи да је та нова вредност једнака \((a_0 + \ldots + a_{m-1}) + a_m + (a_{m+1} + \ldots + a_{i-1})\), што је једнако \(a_0 + \ldots + a_{m'-1}\). Ово је тачно збир свих елемената пре нове позиције максимума за коју смо утврдили да је позиција \(m'=i\). Уједно за све ове елементе важи да су строго мањи од max.
Нова вредност променљиве max једнака је \(a_i\) што јесте нова вредност максимума.
Нова вредност променљиве zbirPosleMax једнака је \(0\), што је једнако збиру вредности \(a_{m'+1} + \ldots + a_{i'-1}\) (јер је \(m' = i\), \(i' = i+1\), па је тај скуп елемената празан).
Претпоставимо да је \(a_i\) мање или једнако од вредности max. Тада се прво појављивање максимума у делу низа \(a_0, \ldots, a_i\) поклапа са првим појављивањем максимума у делу низа \(a_0, \ldots, a_{i-1}\) и налази се такође на позицији \(m\), па је \(m'=m\).
Променљиве max и zbirPreMax не мењају своје вредности (што је у реду, јер је \(m'=m\), па је вредност max једнака \(a_m = a_{m'}\), док је вредност променљиве zbirPreMax једнака \(a_0 + \ldots + a_{m'-1} = a_0 + \ldots + a_{m-1}\)).
Променљива zbirPosleMax увећава своју вредност за \(a_i\), па, пошто је њена стара вредност била једнака \(a_{m+1} + \ldots a_{i-1}\), пошто је \(m'=m\) и \(i'=i+1\), важи да је њена нова вредност једнака \(a_{m+1} + \ldots + a_i = a_{m'+1} + \ldots + a_{i'-1}\).
На крају петље не важи да је \(i < n\), па пошто је \(i \leq n\), важи да је \(i=n\). Зато на основу инваријанте знамо да променљиве zbirPreMax zbirPosleMax заиста имају вредности збира свих елемената пре првог и после првог појављивања максималног елемента у делу низа \(a_0 \ldots a_{i-1}\), што је заправо цео низ (јер је \(i=n\), а \(n\) је укупан број елемената).
#include <iostream>
using namespace std;
int main() {
// ukupan broj predmeta
int n;
cin >> n;
// ucitavanje mase prvog predmeta
int m;
cin >> m;
// najveca do sada ucitana masa
int max = m;
// zbir masa pre najvece do sada ucitane
int zbirPreMax = 0;
// zbir masa posle najvece do sada ucitane
int zbirPosleMax = 0;
for (int i = 1; i < n; i++) {
// ucitavanje mase sledeceg predmeta
cin >> m;
if (m > max) {
// korekcija najvece mase i zbirova
zbirPreMax += max + zbirPosleMax;
max = m;
zbirPosleMax = 0;
} else
zbirPosleMax += m;
}
// prikaz rezultata
cout << zbirPreMax - zbirPosleMax << endl;
return 0;
}