Počet jedniček v podmatici

tady je obrázek

Ahoj,

jde jen o jedničky a nuly, takže bych to viděl nejsnáze takto:

def CountOnes(M,s_1,s_2,r_1,r_2):

#Error checks - r_1>r_2, s1>s_2, r_1,s_1,r_2,s_2 < 0, > rozměr matice

Count = 0;

For i = s_1; i < s_2, i++:

For j = r_1; j < r_2, j++:

if M[j,i] == 1: Count += 1

v případě, že se jedná o matici jedniček a nul, stačí místo předchozího řádku

Count += M[j,i]

return Count

v případě očekávání mnoha dotazů na stejnou matici by se mohlo vyplatit napočítat si čtyřrozměrné pole součtů a pak si jen volat jeho hodnoty. Je to prostorově mnohem náročnější, ale může být výpočetně efektivnější.

Sums = zeros(M_r_count, M_r_count, M_s_count, M_s_count)

For i = 0, i < M_r_count, i++

For j = 0, j < M_c_count, j++

Sums[0 až i, i+1 až konec, 0 až j, j+1 až konec] += M[i,j]

Následně stačí volat

Count = Sums[r_1,r_2,s_1,s_2]

Ahoj Honzo,

casovou a pametovou slozitost \( O(R^2R^2) \) bys asi tezko obhajil :) Kdyz uz, tak pouzijes dynamicke programovani ve slozitosti \( O(RS) \) a kazdy dotaz vyresis v \( O(1) \).