我最近在一家公司接受了面试，但在最后一轮面试中只有一个问题被拒绝了。
面试官陈述了一个长度为n*m的2D阵列。我们可以从左到右从上到下，也可以从对角线上穿过。提供了一个固定的窗口k，以找到遍历任何方式的1d阵列窗口的最大和
数组未排序，也没有任何模式。边缘不可能重叠/滚动
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(
有人能优化我的方法或提供更好的解决方案吗
您可以线性地找到最大子序列。
给定具有k=3的序列2 3 4 5 2从具有sum=9的2 3 4开始，并使用两个索引(一个指向2，一个指向4(将它们转发，从而相应地修改sum：
- 步骤1:
sum=9-2+5=12 - 步骤2:
sum=12-3+2=11
这允许您线性选择max，这比使用n²强力解决方案要好得多
要覆盖主对角线方向，请使用索引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]有关。
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;
}