Write a program to find max sum of K size window in n*m matrix traversing in 8 possible directions l-CodePudding

I recently gave interview at amazon and was rejected in bar raiser round having only one problem.

The interviewer stated a 2D-array of n*m length. We can traverse left right top down as well as both diagonally. A fixed window k was provided to find maximum sum of 1d array window traversing any of the way.

The array is not sorted and doesn't have any pattern. No overlapping/rolling is possible at edges.

1<=n,m<=10^5

Example:- 2 3 4 5 2
          3 1 8 9 9
          4 4 3 2 8 
          3 4 7 7 7
n=4
m=5
k=3

Output :- Max Sum= 26
Explanations:- (8 9 9)
              second row has the largest sum window with size 3.

I gave the brute force approach for traversing all directions(8) along with sliding window approach to calculate the max sum.

Unfortunately I was rejected and I still don't find the optimized solution for the problem made by the interviewer.

CodePudding user response：

You can find the max subsequence linearly.

Given the sequence 2 3 4 5 2 with k=3 start from 2 3 4 with sum=9 and using two indexes - one pointing to 2 and one pointing to 4 - forward them modifying the sum accordingly:

Step 1: sum=9-2 5=12
Step 2: sum=12-3 2=11

This allows you to select the max linearly, which is much better than having a n² brute force solution

CodePudding user response：

public int findMaximumSum(int[][] matrix, int key) {
    int y = matrix.length - 1, x = matrix[0].length - 1;
    int max = 0;
    for (int i = 0; i <= y; i  ) {
        for (int i1 = 0, j = key - 1; j <= x; j  , i1  ) {
            int sum = matrix[i][i1]   matrix[i][j]   matrix[i][(i1   j) / 2];
            max = Math.max(max, sum);
        }
    }
    return max;
}