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