Legjobb O komplexitás?

@Kérdező, ha nem akarsz megoldást látni, akkor ne nézd meg az alábbi pastebin linket.

#20 Gondolom kezdő vagy még te is. Itt egy O(n) megoldás, egyszerű sliding window:

[link]

Ez intuitívabb, mint egy O(y) megoldás, illetve kellően nagy y esetén valószínűleg gyorsabb is.

Ha ezt megérted, akkor könnyen rá kell jönnöd már egy O(y) megoldásra, mert az elv nagyon hasonló.

(C++-ban írtam, ha nem foglalkoztál még ezzel a nyelvvel, akkor a "vector<int> &arr"-t sima int tömbként értelmezheted)

"O(y)-hoz meg egyszerűen csak implementálj egy O(y) megoldást. Elég triviális, nincs szükség hozzá semmi különleges adatstruktúrára vagy algoritmusra."

Hát jó, úgy látom igazad volt.

"Ha ezt megérted, akkor könnyen rá kell jönnöd már egy O(y) megoldásra, mert az elv nagyon hasonló."

Ez meg hogy jött ki?

Pont ez az hogy nem értem ez hogy jön az eredeti kérdésből az ki, de annyit megértettem belőle hogy csinál bizonyos összegzéseket és speciális módon minimum keresést. O(y) futási idejű megoldást ki tudtam belőle hozni, mert látom hogy lespórolható belőle egy while ciklus.

Mármint mi hogy jött ki?

Nem értem, hogy mit nem értesz. A megoldásom elve nem tiszta?

Írtam, hogy egy sima sliding window megoldás.

Mondjuk 10 elemű a tömb és y = 3. Mindegy, hogy jobbról veszünk el 3 elemet, vagy balról, vagy jobbról 2-t és balról 1-et, vagy fordítva. Mivel 3-at veszünk el és azt is csak szélről, mindig 7 egymás melletti elem marad. Ami változik, az ennek a 7 elemnek a pozíciója.

Nevezzük ezt a 7 elemet belsőnek, a maradék 3-at pedig külsőnek.

Arra vagyunk kíváncsiak, hogy a külső elemek összege mikor maximális. Nyilván akkor, amikor a belső elemek összege minimális.

Megkeressük a belső elemek összegének minimumát és kivonjuk az összes elem összegéből, így megkapjuk a külső elemek összegének maximumát.

Azért írtam, hogy ebből könnyen rá kell jönnöd egy O(y) megoldásra, mert az elv ugyanaz, csak az gyakorlatilag az inverze a fenti megoldásnak.

Nem a belső elemek minimumát keresed meg, hanem a külső elemek maximumát.

Mivel eleve az a kérdés, nem kell foglalkozni az összes elem összegével, tehát csak y-tól függ a komplexitás.

Onnantól nem értem hogy mitől a belső elemek összegének minimuma amit csinál az a minimumkeresés. Ha brute force vagy backtrack lenne még érthető lenne.

"Azért írtam, hogy ebből könnyen rá kell jönnöd egy O(y) megoldásra, mert az elv ugyanaz, csak az gyakorlatilag az inverze a fenti megoldásnak."

Akkor lehet nem erre a megoldásra gondoltál. Én azt láttam meg amikor csináltam egy O(y) megoldást belőle, hogy total - best értéke kell. A best és total változó inicializálási értéke tök mindegy mennyi csak az a lényeg hogy egyforma legyen, ezért inicializáltam 0-ra mindkettőt. Az i=w kell ciklus előtt:

[link]

Technikai okokból kicseréltem vector-t mert teszt szkripttel meg ipython shell-ből interaktívan kézzel tesztelem. Nem akarok kínlódni a cppyy-vel, jobb backend-nek a C-vel kompatibilis függvény paraméterek, technikai izék most nem érdekelnek. Az zavar hogy matematikailag nem látom át.

Legyen mondjuk [1, 2, 3, 4, 5] a tömb és k = 2.

Inicializálod az ablakot azzal, hogy összeadod az első 3 elemet (azért 3-at, mert 5 - 2 = 3 az ablak mérete). 1 + 2 + 3 = 6 lesz az ablak összege.

Ezután elkezded jobbra tolni az ablakot. Mivel az ablak mérete fix, ezért minden egyes lépésnél 2 dolog történik:

- egy új elem kerül az ablak elejére

- az ablak végéről kiesik az utolsó elem

Először bejön a 4 és kiesik az 1, tehát 6 + 4 - 1 = 9 lesz az új ablak összege. Aztán bejön az 5 és kiesik a 2, tehát 9 + 5 - 2 = 12 lesz az összeg.

6, 9 és 12 minimuma 6. 1 + 2 + 3 + 4 + 5 = 15. 15 - 6 = 9. Ez a megoldás.