撰寫一個程式，在8個可能的方向線性遍歷的n*m矩陣中找到K大小視窗的最大和

我最近在 amazon 接受了面試，但在 bar raiser 回合中被拒絕了，只有一個問題。

面試官陳述了一個長度為 n*m 的二維陣列。我們可以從左到右從上到下以及對角線遍歷。提供了一個固定的視窗 k 來找到遍歷任何方式的一維陣列視窗的最大和。

該陣列未排序且沒有任何模式。在邊緣處不可能重疊/滾動。

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.

我給出了遍歷所有方向的蠻力方法（8）以及滑動視窗方法來計算最大和。

可惜被拒了，還是沒有找到針對面試官提出的問題的優化方案。

我制作的代碼-

（忽略所需的輸入）

class sliding {
    public static void main(int ar[][], int k) {
        int m = ar.length;
        int n = ar[0].length;
        int sum = 0;

        if (m >= k) { //for row-wise max window
            for (int i = 0; i < m; i  ) {
                int tempSum = 0;
                int x = 0;
                int j = 0;
                while (j < n) {
                    tempSum  = ar[i][j];
                    if (j - x   1 < k)
                        j  ;
                    else if (j - x   1 == k) {
                        sum = Math.max(tempSum, sum);
                        tempSum = tempSum - ar[i][x];
                        x  ;
                        j  ;
                    }
                }
            }
        }
        if (n >= k) //for column-wise max window
        {
            for (int i = 0; i < n; i  ) {
                int tempSum = 0;
                int x = 0;
                int j = 0;
                while (j < m) {
                    tempSum  = ar[i]][j];
                if (j - x   1 < k)
                    j  ;
                else if (j - x   1 == k) {
                    sum = Math.max(tempSum, sum);
                    temSum = tempSum - ar[i][x];
                    x  ;
                    j  ;
                }
            }
        }
    }
    //for diagonal-wise max
    if (n >= k && m >= k) {
        for (int i = 0; i < m; i  ) {
            for (int j = 0; j < n; j  ) {
                int x = 0;
                int p = i;
                int q = j;
                int p_initial = p;
                int q_initial = q;
                int tempSum = 0;
                while (p <= m - k && q <= n - k) {
                    if (x < k) {
                        tempSum  = ar[p  ][q  ];
                        x  ;
                    } else if (x == k) {
                        sum = Math.max(tempSum, sum);
                        tempSum -= ar[p_initial][q_initial];
                        p_initial  ;
                        q_initial  ;
                    }

                }
            }
        }
    }
}// sum variable will store the final answer

復雜度 - O(n^3)

有人可以優化我的方法或提供更好的解決方案。

uj5u.com熱心網友回復：

您可以線性地找到最大子序列。

鑒于序列2 3 4 5 2與k=3從開始2 3 4用sum=9，用兩個指標-一個指向2和一個指向4-他們向前修改sum相應：

• 步驟1： sum=9-2 5=12
• 第2步： sum=12-3 2=11

這允許您max線性選擇，這比使用n2蠻力解決方案要好得多

uj5u.com熱心網友回復：

要覆寫主對角線方向，請使用索引ar[i j][j]而不是ar[i][j]。確保覆寫整個矩陣，同時確保0≤i j<n和0≤j<m。對于給定的j，-j≤i<n-j使外部 for 回圈開啟-m<i<n。內部 while 回圈開啟max(0,-i)≤j<min(n-i,n)。

內部while回圈保持類似的結構，程序仍然是O(nm)。

第二條對角線是ar[i-j][j]。

uj5u.com熱心網友回復：

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;
}

標籤：爪哇 数组 算法 数据结构 滑动窗口

上一篇：查詢圖中的最短路徑演算法

下一篇：圖中有時間限制的最短路徑