Как вычислить подматрицу матрицы

Question

Я давал тест для компании под названием Code Nation и наткнулся на этот вопрос, который попросил меня рассчитать, сколько раз число k появляется в подматрице M [n] [n]. Теперь был пример, который сказал Input вроде этого.

5 
1 2 3 2 5 
36 

M[i][j] состоит в рассчитываются a[i]*a[j] , который на расчет своей очереди, я мог рассчитывать.

1,2,3,2,5 
2,4,6,4,10 
3,6,9,6,15 
2,4,6,4,10 
5,10,15,10,25 

Теперь я должен был подсчитать, сколько раз 36 появляется в суб матрицы М.

Ответ 5.

Я не могу понять, как вычислить эту подматрицы. Как это представить? У меня был наивный подход, который привел к тому, что многие матрицы, по моему мнению, не верны.

Одним из них является подматрица [я] [J]

1 2 3 2 5 
3 9 18 24 39 
6 18 36 60 99 
15 33 69 129 228 
33 66 129 258 486 

Это была образована путем сложения всех чисел до него 0,0 до I, J

В 36 не появилось 5 раз, поэтому я знаю, что это неверно. Если вы можете создать резервную копию с помощью некоторого псевдокода, это будет глазурь на торте.

Цените помощь

[Изменить]: Приглашен После link 1link 2

Answer 1

Я думаю, что вы должны вычислить, сколько подматрицы М имеют сумму, равную 36.

Вот Matlab код :

a=[1,2,3,2,5]; 
n=length(a); 
M=a'*a; 
count = 0; 
for a0 = 1:n 
    for b0 = 1:n 
     for a1 = a0:n 
      for b1 = b0:n 
       A = M(a0:a1,b0:b1); 
       if (sum(A(:))==36) 
        count = count + 1; 
       end 
      end 
     end 
    end 
end 
count 

Это распечатывает 5.

Таким образом, вы правильно вычисления M, но тогда вы должны рассматривать каждую подматрицу М, например, М

1,2,3,2,5 
2,4,6,4,10 
3,6,9,6,15 
2,4,6,4,10 
5,10,15,10,25 

так один возможный подматрица

1,2,3 
2,4,6 
3,6,9 

и если сложить все из них, то сумма равна 36.

Существует answer on cstheory, который дает для этого алгоритм O (n^3).