l********r 发帖数: 140 | 1 Given an n x n matrix A(i,j) of integers, find maximum value A(c,d) - A(a,b)
over all choices of indexes such that both c > a and d > b.
Required complexity: O(n^2)
原题在,可是没有解答。
http://www.careercup.com/question?id=5818131813498880
有大牛看看吗? | y*****g 发帖数: 10 | 2 每个位置记录当前最大差,和最小值(和左上矩阵比)。
每个位置减其左上记录的最小值,如果大于当前最大差,则更新;且,从左上和左及上
位置记录的最小值比较,小于则更新。
3N*N | b*****c 发帖数: 1103 | | x*****a 发帖数: 9 | 4 spaceO(n*n), timeO(n*n)
an extra matrix named max
max(x,y) = max value of the sub matrix with left-top at (x,y) | g*****g 发帖数: 212 | 5 here is the code
int maxInMatrix(vector> &matrix)
{
int n = matrix.size();
int m = matrix[0].size();
vector premin(m+1, INT_MAX);
int maxdiff = 0;
for(int i=0; i
{
vector curmin(m+1, INT_MAX);
for(int j=0; j
{
curmin[j+1] = min(premin[j+1], curmin[j], matrix[i][j]);
int diff = matrix[i][j] - curmin[j+1];
if (diff > maxdiff)
maxdiff = diff;
}
premin = curmin;
}
return maxdiff;
}
b)
【在 l********r 的大作中提到】 : Given an n x n matrix A(i,j) of integers, find maximum value A(c,d) - A(a,b) : over all choices of indexes such that both c > a and d > b. : Required complexity: O(n^2) : 原题在,可是没有解答。 : http://www.careercup.com/question?id=5818131813498880 : 有大牛看看吗?
| S********e 发帖数: 74 | 6 铁一下这个算法的code
int maxSub(std::vector > &matrix)
{
std::vector store(matrix.size(),INT_MAX);
int max_sub=INT_MIN;
for (int r=1; r
{
for (int c=1; c
{
store[c]=std::min(matrix[r-1][c-1],std::min(store[c-1],store[c])
);
max_sub = std::max(max_sub,matrix[r][c]-store[c]);
}
}
return max_sub;
}
【在 y*****g 的大作中提到】 : 每个位置记录当前最大差,和最小值(和左上矩阵比)。 : 每个位置减其左上记录的最小值,如果大于当前最大差,则更新;且,从左上和左及上 : 位置记录的最小值比较,小于则更新。 : 3N*N
|
|