Description

Given an array of n_m matrix, and a moving matrix window (size k_k), move the window from top left to botton right at each iteration, find the maximum sum of the elements inside the window at each moving. Return 0 if the answer does not exist.

Example

For matrix [ [1, 5, 3], [3, 2, 1], [4, 1, 9], ]. The moving window size k = 2.return 13. At first the window is at the start of the array like this [ [|1, 5|, 3], [|3, 2|, 1], [4, 1, 9], ] ,get the sum 11; then the window move one step forward. [ [1, |5, 3|], [3, |2, 1|], [4, 1, 9], ] ,get the sum 11; then the window move one step forward again. [ [1, 5, 3], [|3, 2|, 1], [|4, 1|, 9], ] ,get the sum 10; then the window move one step forward again. [ [1, 5, 3], [3, |2, 1|], [4, |1, 9|], ] ,get the sum 13; SO finally, get the maximum from all the sum which is 13.

Challenge

O(n^2) time.

Solution

1. 先想了一个蠢方法，window的右下角从(k-1, k-1)走到(n-1, m-1), 走弓字型，用一个bool的flag记录平移的方向，那么他有三个方向的移动： j<m时右移，sum + (matrix[i-k+1][j] + ... + matrix[i][j]) - (matrix[i-k+1][j-k] + ... + matrix[i][j-k]) i <n时下移， sum + (matrix[i][j-k+1] + ... + matrix[i][j]) - (matrix[i-k][j-k+1] + ... + matrix[i-k][j]) j>=0时左移， sum + (matrix[i-k+1][j-k+1] + ... + matrix[i][j-k+1]) - (matrix[i=k+1][j-1] + matrix[i][j-1])
2. 用sum matrix就可以很简单的解决 初始化给sum matrix左边和上边各加一条index为0 sum为0的边 sum[i][j] = matrix[i - 1][j - 1] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] matrix[i][j] = sum[i][j] - sum[i - k][j] - sum[i][j - k] + sum[i - k][j - k]; i >= k; j >= k