Hogy kell lekódolni?
Van egy N elemű int tömb és egy K szám (N <= 10000, K <= 10).
Mennyi a tömbből maximálisan kiválasztható összeg ha bármennyi elemet kiválaszthatunk de maximum K db lehet egymást követő?
Pl [1, 2, 3, 4] a tömb és K = 2 akkor 8 a válasz.
#1-es vagyok nem biztos hogy a legjobb megoldás (de mindenki jobban szeret kijavítani másokat mint kérdésre válaszolni)
Csinálj egy ciklust ami addig megy míg a vektor szummája 0 vagy kevesebb
ha ez hamis (vagyis nagyobb mint 0) akkor keresd meg a legnagyobb elemet és vizsgáld meg hogy mellette balra jobbra van e összesen K mennyiségű nulla ha van akkor csak állítsd át -1-re ha nincs akkor add hozzá a változóhoz ami majd az eredményt adja és állítsd át nullára a vektorban
Szóval a te példáddal az [1, 2, 3, 4] vektor K = 2
Max(v) = 4
az indextől balra (jobbra nem mehet ha vektor vége/nincs több elem) az i-1 és i-K elemek nem nullák így a szumma = 4 és lenullázzuk
Marad a [1, 2, 3, 0] vektor ahol a max a 3, megint nincs elég nulla balra jobbra így szumma = szumma+3;
marad az [1, 2, 0, 0] ugye a maximum a 2 lenne de mivel jobbra már megvan a K mennyiségű nulla így 0 helyett -1-re állítjuk
[1, -1, 0, 0] ből a max az 1 ami mellett nincs meg az elég 0 így a szumma = szumma+1; és a végén megkapjuk a [0, -1, 0, 0] vektor
Így kijön a nyolc és a ciklus leállhat mert a vektor szummája -1
nem tudom milyen nyelvben kéne neked ezért csak így szövegesen (remélem érthetően) leírtam
12-es én Javaban próbálkozok.
13-as nem biztos hogy jól értem, de ha 0 és -1 van a tömbben akkor ez nem működik szerintem.
Pl lehet mondjuk [-5, -1, -10, -1] a tömb, ekkor ugye -1 a megoldás.
Vagy lehet pl [5, -10000, 25] és mondjuk K = 3. Ekkor a szumma eleve negatív de a megoldás 30.
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!