Precomputing the number of 1 s
int ones [ ] [ ] = new int [ R + 1 ] [ C + 1 ] ; for ( int i = 1 ; i <= R ; i ++ ) for ( int j = 1 ; j <= C ; j ++ ) { if ( mat [ i - 1 ] [ j - 1 ] == 1 ) val = 1 ; ones [ i ] [ j ] = ones [ i - 1 ] [ j ] + ones [ i ] [ j - 1 ] - ones [ i - 1 ] [ j - 1 ] + ( val ) ; }