Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#1 13. 03. 2015 09:27
Výřez matice (2D pole) splňující podmínky
Dobrý den,
mám 2 problémy týkající se maximálního výřezu z čtvercové matice, výřez může být obdélník a zajímá mě jeho umístění ne jen velikost. Nepotřebuji přímo kód ale nějaký postup jak tento problém efektivně řešit.
1. Matice obsahuje jen 1 a 0, hledám výřez obsahující jen 1 (existuje řešení O(n^2), stačí O(n^3) )
2. Matice obsahuje kladné i záporné hodnoty, hledám výřez kde součet všech prvků ve výřezu je menší než hodnota k (řešení by mělo mít složitost O(n^4)
Pokud dobře chápu tak úloha vede na largest rectangle problem.
Děkuji za odpovědi
Offline