Milyen algoritmussal oldanád meg az alábbi feladatot?

Maradjunk ennel a peldanal:

7 2 4 17 6 5 13 10 18 19

Megvan hozza a suffix min tombunk, O(n) komplexitassal:

sMin = [2, 2, 4, 5, 5, 5, 10, 10, 18, 19]

Ez ugye megmutatja, hogy adott indexen mi a legkisebb elerheto ertek a suffixban.

Mi van ha meg tudnank mondani, hogy adott indexen mi a legnagyobb elerheto ertek a prefixben?

Generaljuk le a suffix min mellett a prefix maxot is, szinten O(n) komplexitassal:

pMax = [7, 7, 7, 17, 17, 17, 17, 17, 18, 19]

A bemeneti tombot el is felejthetjuk.

Mi a celunk? Megtalalni azt az i es j indexpart, ahol pMax[i] > sMin[j] es j - i a legnagyobb.

Mivel mindket tombunk rendezett, ezt szinten megtehetjuk O(n) komplexitassal. Elindulunk a 0 indexrol, ha pMax[i] > sMin[j] akkor ++j, egyebkent ++i, ameddig el nem erjuk valamelyik tomb veget (tovabb nyilvan nem erdemes vizsgalni, hiszen ha pMax vegen vagyunk, akkor j - i maximum 0 lehet, ha sMin vegen, akkor pedig nem letezik jobb megoldas az eddig megtalaltnal, mert j - i mar csak csokkenhet).

A példánál maradva az O(N*log(N)) és az O(N) megoldás be és kimenete:

Be : 7 2 4 17 6 5 13 10 18 1

Ki :

7 5

5

----

2 13

5

Meg van még ahol jó megoldást ad az O(N), de pl ennél nem:

szintén mind a két módszer szerint:

Be:

2 6 4 8 1 5 7 10 3 9

Ki:

6 3

7

----

6 9

8

A két generált segédtömb:

s min = 1, 1, 1, 1, 1, 3, 3, 3, 3, 9

p max = 2, 6, 6, 8, 8, 8, 8, 10, 10, 10

Ezek szerint nem jol implementaltad.

En megirtam most gyorsan az O(N)-t C++-ban.

[7, 2, 4, 17, 6, 5, 13, 10, 18, 1]:

7, 1

9

[2, 6, 4, 8, 1, 5, 7, 10, 3, 9]

6, 3

7

Ha megosztod a kododat megmondom, hol a hiba.

Mobilról vagyok, de így ránézésre te a tényleges indexekkel számolsz. Ha van mondjuk a prefix tömbben 4db 1-es egymás mellett, az nyilván ugyanahhoz az indexhez tartozik a bemeneti tömbben. Érdemes letárolni az értékek mellett az indexeket is.

De ha ilyen szintű nehézséget okoz neked ez a feladat, akkor inkább könnyebbekkel kellene foglalkoznod először.

Persze hogy az indexekkel számolok, hiszen hogy máshogy tudnám a távolságot mint az indexeik alapján. Egyébként te írtad : "A bemeneti tombot el is felejthetjuk."

"Mi a celunk? Megtalalni azt az i es j indexpart, ahol pMax[i] > sMin[j] es j - i a legnagyobb.

Mivel mindket tombunk rendezett, ezt szinten megtehetjuk O(n) komplexitassal. Elindulunk a 0 indexrol, ha pMax[i] > sMin[j] akkor ++j, egyebkent ++i, ameddig el nem erjuk valamelyik tomb veget (tovabb nyilvan nem erdemes vizsgalni, hiszen ha pMax vegen vagyunk, akkor j - i maximum 0 lehet, ha sMin vegen, akkor pedig nem letezik jobb megoldas az eddig megtalaltnal, mert j - i mar csak csokkenhet)."

Ebben mit nem csináltam úgy mint a specifikáció amit írtál?

Nem specifikációt írtam, hanem az ötletet, amiből ki tudsz indulni.

De ha ennyi segítséggel sem tudod megoldani, akkor felejtsd el ezt a feladatot, nem neked való még. Az alapokat tanuld.

A könnyebb feladatok nem kihívások, egyébként jó megoldást ad az O(N*log(N))-es megoldás ezen esetekre (is), amit ide bemásoltam mint kimentet hibásan másoltam be, de ha bárki is vette volna a fáradságot amit az ideone-ra feltöltöttem akkor rájöhetett volna. A hibát a fáradság és a python interpreterbe valami elgépelés okozhatta a hibát. Mint említettem múltkor is : "Csak a python interpreterébe irkáltam és futtattam, külön fájlba nem is mentettem ki a szkirptet,".

Konkrétan az O(N)-es megoldásra senki nem tudta megírni eddig hogy konkrétan azért nem jó mert ... . Konkrétan rámutatásra gondoltam, hogy ebben tér el a specifikációtól.

A konnyebb feladatok nem kihivasok, errol meg fingod nincs ennyi segitseggel, pedig mar annyibol rajohettel volna a megoldasra, hogy prefix maxot es suffix mint hasznalok.

Ahelyett, hogy itt pattogsz, inkabb debuggold a megoldasodat, en nem fogom helyetted.

Mar [6, 4]-re is rossz megoldast ad, egy 2 elemu tombnel talan kepes vagy rajonni, hogy mi lehet a problema.