买了一台cvs的netbook - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>PennySaver - 省钱一族

买了一台cvs的netbook

买了一台cvs的netbook# PennySaver - 省钱一族

l*r2010-09-04 07:09

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
有大牛看看吗？

c*a2010-09-04 07:09

2 楼

配置确实不好
128 M ram
800x480 pixels
win ce 6.0
但是才2磅，而且有usb和读卡器，开机很快
今天去的一家cvs就2台货，还没上架

y*g2010-09-04 07:09

3 楼

每个位置记录当前最大差，和最小值（和左上矩阵比）。
每个位置减其左上记录的最小值，如果大于当前最大差，则更新；且，从左上和左及上
位置记录的最小值比较，小于则更新。
3N*N

w*i2010-09-04 07:09

4 楼

据说不能打coupons。com的哭胖？

b*c2010-09-04 07:09

5 楼

扫一遍啊O(n)的空间

l*e2010-09-04 07:09

6 楼

baozi!
liujie congrats you!

x*a2010-09-04 07:09

7 楼

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)

c*a2010-09-04 07:09

8 楼

我帮同学买的，在她家（学校的无线网），ms上不了。。。
所以能不能打coupon也不知道。。。

【在 w******i 的大作中提到】

: 据说不能打coupons。com的哭胖？

g*g2010-09-04 07:09

9 楼

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
: 有大牛看看吗？

c*52010-09-04 07:09

10 楼

128m 能干啥呀。。。

S*e2010-09-04 07:09

11 楼

铁一下这个算法的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