Given an n x n square matrix , find sum of all sub | Size of given matrix ; A O ( n ^ 2 ) function to find sum of all sub - squares of size k x k in a given square matrix of size n x n ; k must be smaller than or equal to n ; 1 : PREPROCESSING To store sums of all strips of size k x 1 ; Go column by column ; Calculate sum of first k x 1 rectangle in this column ; Calculate sum of remaining rectangles ; 2 : CALCULATE SUM of Sub - Squares using stripSum [ ] [ ] ; Calculate and print sum of first subsquare in this row ; Calculate sum of remaining squares in current row by removing the leftmost strip of previous sub - square and adding a new strip ; Driver Code
< ? php $ n = 5 ; function printSumTricky ( $ mat , $ k ) { global $ n ; if ( $ k > $ n ) return ; $ stripSum = array ( array ( ) ) ; for ( $ j = 0 ; $ j < $ n ; $ j ++ ) { $ sum = 0 ; for ( $ i = 0 ; $ i < $ k ; $ i ++ ) $ sum += $ mat [ $ i ] [ $ j ] ; $ stripSum [ 0 ] [ $ j ] = $ sum ; for ( $ i = 1 ; $ i < $ n - $ k + 1 ; $ i ++ ) { $ sum += ( $ mat [ $ i + $ k - 1 ] [ $ j ] - $ mat [ $ i - 1 ] [ $ j ] ) ; $ stripSum [ $ i ] [ $ j ] = $ sum ; } } for ( $ i = 0 ; $ i < $ n - $ k + 1 ; $ i ++ ) { $ sum = 0 ; for ( $ j = 0 ; $ j < $ k ; $ j ++ ) $ sum += $ stripSum [ $ i ] [ $ j ] ; echo $ sum , " " ; for ( $ j = 1 ; $ j < $ n - $ k + 1 ; $ j ++ ) { $ sum += ( $ stripSum [ $ i ] [ $ j + $ k - 1 ] - $ stripSum [ $ i ] [ $ j - 1 ] ) ; echo $ sum , " " ; } echo " STRNEWLINE " ; } } $ mat = array ( array ( 1 , 1 , 1 , 1 , 1 ) , array ( 2 , 2 , 2 , 2 , 2 ) , array ( 3 , 3 , 3 , 3 , 3 ) , array ( 4 , 4 , 4 , 4 , 4 ) , array ( 5 , 5 , 5 , 5 , 5 ) ) ; $ k = 3 ; printSumTricky ( $ mat , $ k ) ; ? >