有谁用电视卡，在电脑显示器上看电视的吗？# Living
s*t
1 楼
一个matrix，每个matrix[i][j]有一个价格，给你一个budget，问如何求出最大面积的
子矩阵，使得子矩阵的价格之和不超过budget
没有想到特别好的解法
子矩阵，使得子矩阵的价格之和不超过budget
没有想到特别好的解法
T*7
2 楼
对面的一个理财的公司，说是ABC老夫妇，年终之前还是想给儿孙拼搏一下的。没想到
直接把钱都掉里面了。而且因为他们签约的时候他们自己没注意，要是亏损一定要自负
盈亏的那种，就是有问题也不能找这个公司。弄的夫妻俩存的那些钱都没有了。而且是
彻底的，这对儿还算是好的没贷款，前段时间还有一对儿年轻人贷款了那个叫一个惨，
但是是正常买卖，警察来了也不会怎么样，你就算是请什么人来都一样，只能自认倒霉。
可怜这对儿夫妻天天来公司问，天天在公司这里忍着，没有椅子也没有什么地方坐着就
坐在地上，我们偶尔看到还会帮着给倒点热水什么的。真的是挺可怜的。
要说投资这种东西还是一定要自己搞明白再下去吧，要不这样了自然是不会幸福的。何
况家里的孩子还不知道，要是知道了指不定要怎么生气。要是闹出事来还不知道要怎么
样才能收场呢。
直接把钱都掉里面了。而且因为他们签约的时候他们自己没注意，要是亏损一定要自负
盈亏的那种，就是有问题也不能找这个公司。弄的夫妻俩存的那些钱都没有了。而且是
彻底的，这对儿还算是好的没贷款，前段时间还有一对儿年轻人贷款了那个叫一个惨，
但是是正常买卖，警察来了也不会怎么样，你就算是请什么人来都一样，只能自认倒霉。
可怜这对儿夫妻天天来公司问，天天在公司这里忍着，没有椅子也没有什么地方坐着就
坐在地上，我们偶尔看到还会帮着给倒点热水什么的。真的是挺可怜的。
要说投资这种东西还是一定要自己搞明白再下去吧，要不这样了自然是不会幸福的。何
况家里的孩子还不知道，要是知道了指不定要怎么生气。要是闹出事来还不知道要怎么
样才能收场呢。
J*S
3 楼
以前是， 觉得特别方便，可以看到节目单， 可以定时录像。
我把巨无霸天线架上了，现在电视可以收到20来个台，刚满足需要。出了两个太不稳定
，其他的还行。
可是我用的电脑显示器看的TV，多数台比较卡。 难道是我的电视卡，落伍了。 以前是
电视信号强，所以没问题。现在信号弱，就卡了？
我把巨无霸天线架上了，现在电视可以收到20来个台，刚满足需要。出了两个太不稳定
，其他的还行。
可是我用的电脑显示器看的TV，多数台比较卡。 难道是我的电视卡，落伍了。 以前是
电视信号强，所以没问题。现在信号弱，就卡了？
J*a
4 楼
这题看起来和leetcode的Maximal Rectangle 很像，但似乎不可能找到类似的复杂度的
解法。
能想到的solution
1.preprocess：建立一个matrix［］［］存［0］［0］到［i］［j］的sum，这个可以
用dp解决，复杂度O（n^2）
2.check 以每一点为右下点的最大可能的矩阵，这个每个点都是O（i＊lg（j））的复
杂度了吧。除了可以用个binary search来减少一点复杂度，我也想不到别的办法了。
解法。
能想到的solution
1.preprocess：建立一个matrix［］［］存［0］［0］到［i］［j］的sum，这个可以
用dp解决，复杂度O（n^2）
2.check 以每一点为右下点的最大可能的矩阵，这个每个点都是O（i＊lg（j））的复
杂度了吧。除了可以用个binary search来减少一点复杂度，我也想不到别的办法了。
a*g
5 楼
就怕这种，还回头被人打的跟落水狗一样
a9
6 楼
电视卡是比电视收信号差一些。
【在 J**S 的大作中提到】
: 以前是， 觉得特别方便，可以看到节目单， 可以定时录像。
: 我把巨无霸天线架上了，现在电视可以收到20来个台，刚满足需要。出了两个太不稳定
: ，其他的还行。
: 可是我用的电脑显示器看的TV，多数台比较卡。 难道是我的电视卡，落伍了。 以前是
: 电视信号强，所以没问题。现在信号弱，就卡了？
【在 J**S 的大作中提到】
: 以前是， 觉得特别方便，可以看到节目单， 可以定时录像。
: 我把巨无霸天线架上了，现在电视可以收到20来个台，刚满足需要。出了两个太不稳定
: ，其他的还行。
: 可是我用的电脑显示器看的TV，多数台比较卡。 难道是我的电视卡，落伍了。 以前是
: 电视信号强，所以没问题。现在信号弱，就卡了？
w*1
7 楼
如果是要找是一个region，形状可以不规则。。。
只能是LZ运气不好了，这么难的题，就算你知道怎么做，20分钟谁都不好说能写出bug
free吧。。。讲清思路都不错了
再碰到个有口音的面试官，你边讲边写，他还要挑你的错，想想都头大。。。
只能是LZ运气不好了，这么难的题，就算你知道怎么做，20分钟谁都不好说能写出bug
free吧。。。讲清思路都不错了
再碰到个有口音的面试官，你边讲边写，他还要挑你的错，想想都头大。。。
x*i
8 楼
这不是国内吗？
J*S
9 楼
都是TV TUNER，是不是好点的电视卡，就好点？
【在 a9 的大作中提到】
: 电视卡是比电视收信号差一些。
【在 a9 的大作中提到】
: 电视卡是比电视收信号差一些。
s*r
10 楼
sln 1: brute force
calculate cost for every possible rectangle and return the maximum rectangle
within budget.
complexity: O(n^6)
O(n^4) rectangles and calc cost for each rectangle is O(n^2)
sln2: O(n^4)
1)fix left and right column of matrix (O(n^2) possibilities)
2)for each fixed left and right column
a)for each row, calc the cost from left to right, as tmp[i] O(n^2)
b)given 1D array tmp[], find the longest sub-array within budget, can be
done in O(n)
complexity: O(n^4)
sln3: O(n^3)
in sln2 step 2)a) can be optimized to O(n) if we aggregate it from previous
loop.
简单写了一下sln3的code：
如果只须返回最大面积 把 sub[][]和 y[]相关code去掉即可
public int findMaxLen(int []arr,int budget, int []y){
int maxLen=0;
int sum=0;
int start=0;
for(int i=0;i
if(sum<=budget){
if(i-start+1>maxLen){
maxLen=i-start+1;
y[0]=start;
y[1]=i;
}
}
else{
while(start<=i&&sum>budget)
sum-=arr[start++];
}
}
return maxLen;
}
//int [][]sub=new int[2][2]; top-left, right-bottom corners of the sub-
matrix
public int findMaxRectangle(int [][]matrix, int budget, int [][]sub){
int maxArea=0;
int m=matrix.length;
int n=matrix[0].length;
int []tmp=new int[m];
int []y=new int[2];
for(int left=0;left
for(int right=left;right
int maxLen = findMaxLen(tmp,budget,y);
int area= (right-left+1)*maxLen;
if(area>maxArea){
maxArea=area;
sub[0][0]=left;
sub[0][1]=y[0];
sub[1][0]=right;
sub[1][1]=y[1];
}
}
}
return maxArea;
}
calculate cost for every possible rectangle and return the maximum rectangle
within budget.
complexity: O(n^6)
O(n^4) rectangles and calc cost for each rectangle is O(n^2)
sln2: O(n^4)
1)fix left and right column of matrix (O(n^2) possibilities)
2)for each fixed left and right column
a)for each row, calc the cost from left to right, as tmp[i] O(n^2)
b)given 1D array tmp[], find the longest sub-array within budget, can be
done in O(n)
complexity: O(n^4)
sln3: O(n^3)
in sln2 step 2)a) can be optimized to O(n) if we aggregate it from previous
loop.
简单写了一下sln3的code：
如果只须返回最大面积 把 sub[][]和 y[]相关code去掉即可
public int findMaxLen(int []arr,int budget, int []y){
int maxLen=0;
int sum=0;
int start=0;
for(int i=0;i
if(sum<=budget){
if(i-start+1>maxLen){
maxLen=i-start+1;
y[0]=start;
y[1]=i;
}
}
else{
while(start<=i&&sum>budget)
sum-=arr[start++];
}
}
return maxLen;
}
//int [][]sub=new int[2][2]; top-left, right-bottom corners of the sub-
matrix
public int findMaxRectangle(int [][]matrix, int budget, int [][]sub){
int maxArea=0;
int m=matrix.length;
int n=matrix[0].length;
int []tmp=new int[m];
int []y=new int[2];
for(int left=0;left
for(int right=left;right
int maxLen = findMaxLen(tmp,budget,y);
int area= (right-left+1)*maxLen;
if(area>maxArea){
maxArea=area;
sub[0][0]=left;
sub[0][1]=y[0];
sub[1][0]=right;
sub[1][1]=y[1];
}
}
}
return maxArea;
}
s*r
11 楼
又是器人帖？ 买买提在这样下去估计是活人越来越少了。现在大部分版面基本全
是没营养的器人帖。
是没营养的器人帖。
a9
12 楼
电视卡那么小个东西，怎么都比不上大电视里的tuner的。
【在 J**S 的大作中提到】
: 都是TV TUNER，是不是好点的电视卡，就好点？
【在 J**S 的大作中提到】
: 都是TV TUNER，是不是好点的电视卡，就好点？
b*b
13 楼
this can be solved in n^2 using dp. busy now, can write shortly about my
thought.
for each point (i, j), we need to keep track of 2 things,
what's the biggest rectangle starting i,j go horizontally, and what's the
biggest rectangle go vertically, you need to keep both instead of just keep
the
max one.
for f(i+1, j+1), check whether add the row/col to the horizonal one will be
bigger than target, if not, increase it, otherwise remove one row/col. do
same thing for vertical one. You need to calculate a sum array of each row/
col to easily calculate interval sum for any row/col.
actually the code should not be very complicate, i think i can write one
with bug (not bug free) in 10-15 minutes. will get back to this when get a
break.
rectangle
【在 s*******r 的大作中提到】
: sln 1: brute force
: calculate cost for every possible rectangle and return the maximum rectangle
: within budget.
: complexity: O(n^6)
: O(n^4) rectangles and calc cost for each rectangle is O(n^2)
: sln2: O(n^4)
: 1)fix left and right column of matrix (O(n^2) possibilities)
: 2)for each fixed left and right column
: a)for each row, calc the cost from left to right, as tmp[i] O(n^2)
: b)given 1D array tmp[], find the longest sub-array within budget, can be
thought.
for each point (i, j), we need to keep track of 2 things,
what's the biggest rectangle starting i,j go horizontally, and what's the
biggest rectangle go vertically, you need to keep both instead of just keep
the
max one.
for f(i+1, j+1), check whether add the row/col to the horizonal one will be
bigger than target, if not, increase it, otherwise remove one row/col. do
same thing for vertical one. You need to calculate a sum array of each row/
col to easily calculate interval sum for any row/col.
actually the code should not be very complicate, i think i can write one
with bug (not bug free) in 10-15 minutes. will get back to this when get a
break.
rectangle
【在 s*******r 的大作中提到】
: sln 1: brute force
: calculate cost for every possible rectangle and return the maximum rectangle
: within budget.
: complexity: O(n^6)
: O(n^4) rectangles and calc cost for each rectangle is O(n^2)
: sln2: O(n^4)
: 1)fix left and right column of matrix (O(n^2) possibilities)
: 2)for each fixed left and right column
: a)for each row, calc the cost from left to right, as tmp[i] O(n^2)
: b)given 1D array tmp[], find the longest sub-array within budget, can be
b*b
14 楼
I think i'm wrong, its still n^3 because i cannot just keep track of 2, but
instead need to keep track a list of the rectangles with i,j as top left
corner.
keep
be
【在 b******b 的大作中提到】
: this can be solved in n^2 using dp. busy now, can write shortly about my
: thought.
: for each point (i, j), we need to keep track of 2 things,
: what's the biggest rectangle starting i,j go horizontally, and what's the
: biggest rectangle go vertically, you need to keep both instead of just keep
: the
: max one.
: for f(i+1, j+1), check whether add the row/col to the horizonal one will be
: bigger than target, if not, increase it, otherwise remove one row/col. do
: same thing for vertical one. You need to calculate a sum array of each row/
instead need to keep track a list of the rectangles with i,j as top left
corner.
keep
be
【在 b******b 的大作中提到】
: this can be solved in n^2 using dp. busy now, can write shortly about my
: thought.
: for each point (i, j), we need to keep track of 2 things,
: what's the biggest rectangle starting i,j go horizontally, and what's the
: biggest rectangle go vertically, you need to keep both instead of just keep
: the
: max one.
: for f(i+1, j+1), check whether add the row/col to the horizonal one will be
: bigger than target, if not, increase it, otherwise remove one row/col. do
: same thing for vertical one. You need to calculate a sum array of each row/
l*s
15 楼
不错
【在 J*********a 的大作中提到】
: 这题看起来和leetcode的Maximal Rectangle 很像，但似乎不可能找到类似的复杂度的
: 解法。
: 能想到的solution
: 1.preprocess：建立一个matrix［］［］存［0］［0］到［i］［j］的sum，这个可以
: 用dp解决，复杂度O（n^2）
: 2.check 以每一点为右下点的最大可能的矩阵，这个每个点都是O（i＊lg（j））的复
: 杂度了吧。除了可以用个binary search来减少一点复杂度，我也想不到别的办法了。
【在 J*********a 的大作中提到】
: 这题看起来和leetcode的Maximal Rectangle 很像，但似乎不可能找到类似的复杂度的
: 解法。
: 能想到的solution
: 1.preprocess：建立一个matrix［］［］存［0］［0］到［i］［j］的sum，这个可以
: 用dp解决，复杂度O（n^2）
: 2.check 以每一点为右下点的最大可能的矩阵，这个每个点都是O（i＊lg（j））的复
: 杂度了吧。除了可以用个binary search来减少一点复杂度，我也想不到别的办法了。
b*b
16 楼
n^3 is the best solution i can think up with, anyone have better idea?
【在 l******s 的大作中提到】
: 不错
【在 l******s 的大作中提到】
: 不错
l*s
17 楼
二楼的思路我觉得有可能做到O(2 * lgN * N2)，只是那个第二步的B-Search有点麻烦
，因为是B-search一块Matrix。
【在 b******b 的大作中提到】
: n^3 is the best solution i can think up with, anyone have better idea?
，因为是B-search一块Matrix。
【在 b******b 的大作中提到】
: n^3 is the best solution i can think up with, anyone have better idea?
e*3
18 楼
没懂2, 能详细点不?怎么得到ilog(j)的负责度
【在 J*********a 的大作中提到】
: 这题看起来和leetcode的Maximal Rectangle 很像，但似乎不可能找到类似的复杂度的
: 解法。
: 能想到的solution
: 1.preprocess：建立一个matrix［］［］存［0］［0］到［i］［j］的sum，这个可以
: 用dp解决，复杂度O（n^2）
: 2.check 以每一点为右下点的最大可能的矩阵，这个每个点都是O（i＊lg（j））的复
: 杂度了吧。除了可以用个binary search来减少一点复杂度，我也想不到别的办法了。
J*a
19 楼
//area[i][j] is value sum of [0][0]-[i][j];
public int val_cals(a,i,j-1,j) {
return area[i][j] - area[a][j] - area[i][j - 1] + area[a][j - 1];
}
//This is the calculation of max_area for each right-bottom point (i,j).
for (int a = i - 1; a >= 0; a++) {
if (val_cals(a,i, j-1,j) > target) break;
int low = 0;
int high = j - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (val_cals(a, i, mid, j) > target) low = mid + 1;
else if (val_cals(a, i, mid, j) < target) high = mid - 1;
else {
global_max = Math.max(global_max, (j - mid) * (i - a));
break;
}
}
}
//need to calculate for n*n points to get the global max.
Probably there is some bug.
【在 e********3 的大作中提到】
:
: 没懂2, 能详细点不?怎么得到ilog(j)的负责度
public int val_cals(a,i,j-1,j) {
return area[i][j] - area[a][j] - area[i][j - 1] + area[a][j - 1];
}
//This is the calculation of max_area for each right-bottom point (i,j).
for (int a = i - 1; a >= 0; a++) {
if (val_cals(a,i, j-1,j) > target) break;
int low = 0;
int high = j - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (val_cals(a, i, mid, j) > target) low = mid + 1;
else if (val_cals(a, i, mid, j) < target) high = mid - 1;
else {
global_max = Math.max(global_max, (j - mid) * (i - a));
break;
}
}
}
//need to calculate for n*n points to get the global max.
Probably there is some bug.
【在 e********3 的大作中提到】
:
: 没懂2, 能详细点不?怎么得到ilog(j)的负责度
b*b
20 楼
for every point right-bottom at (i, j), it's total n^2 points, and each
point is nlogn, so total it's n^3logn, is it even worse than the n^3?
【在 J*********a 的大作中提到】
: //area[i][j] is value sum of [0][0]-[i][j];
: public int val_cals(a,i,j-1,j) {
: return area[i][j] - area[a][j] - area[i][j - 1] + area[a][j - 1];
: }
: //This is the calculation of max_area for each right-bottom point (i,j).
: for (int a = i - 1; a >= 0; a++) {
: if (val_cals(a,i, j-1,j) > target) break;
: int low = 0;
: int high = j - 1;
: while (low <= high) {
point is nlogn, so total it's n^3logn, is it even worse than the n^3?
【在 J*********a 的大作中提到】
: //area[i][j] is value sum of [0][0]-[i][j];
: public int val_cals(a,i,j-1,j) {
: return area[i][j] - area[a][j] - area[i][j - 1] + area[a][j - 1];
: }
: //This is the calculation of max_area for each right-bottom point (i,j).
: for (int a = i - 1; a >= 0; a++) {
: if (val_cals(a,i, j-1,j) > target) break;
: int low = 0;
: int high = j - 1;
: while (low <= high) {
T*U
21 楼
这个函数要改一下
public int val_cals(a,i,b,j) {
return area[i][j] - area[a][j] - area[i][b] + area[a][b];
}
复杂度加上i, j的外层循环，应该是n3logn了
【在 J*********a 的大作中提到】
: //area[i][j] is value sum of [0][0]-[i][j];
: public int val_cals(a,i,j-1,j) {
: return area[i][j] - area[a][j] - area[i][j - 1] + area[a][j - 1];
: }
: //This is the calculation of max_area for each right-bottom point (i,j).
: for (int a = i - 1; a >= 0; a++) {
: if (val_cals(a,i, j-1,j) > target) break;
: int low = 0;
: int high = j - 1;
: while (low <= high) {
public int val_cals(a,i,b,j) {
return area[i][j] - area[a][j] - area[i][b] + area[a][b];
}
复杂度加上i, j的外层循环，应该是n3logn了
【在 J*********a 的大作中提到】
: //area[i][j] is value sum of [0][0]-[i][j];
: public int val_cals(a,i,j-1,j) {
: return area[i][j] - area[a][j] - area[i][j - 1] + area[a][j - 1];
: }
: //This is the calculation of max_area for each right-bottom point (i,j).
: for (int a = i - 1; a >= 0; a++) {
: if (val_cals(a,i, j-1,j) > target) break;
: int low = 0;
: int high = j - 1;
: while (low <= high) {
J*a
22 楼
Right, but that is what I can reach.
I'd like to study the better solution, if you could code yours.
【在 b******b 的大作中提到】
: for every point right-bottom at (i, j), it's total n^2 points, and each
: point is nlogn, so total it's n^3logn, is it even worse than the n^3?
I'd like to study the better solution, if you could code yours.
【在 b******b 的大作中提到】
: for every point right-bottom at (i, j), it's total n^2 points, and each
: point is nlogn, so total it's n^3logn, is it even worse than the n^3?
d*1
23 楼
价格都是正数吗？
【在 s*******t 的大作中提到】
: 一个matrix，每个matrix[i][j]有一个价格，给你一个budget，问如何求出最大面积的
: 子矩阵，使得子矩阵的价格之和不超过budget
: 没有想到特别好的解法
【在 s*******t 的大作中提到】
: 一个matrix，每个matrix[i][j]有一个价格，给你一个budget，问如何求出最大面积的
: 子矩阵，使得子矩阵的价格之和不超过budget
: 没有想到特别好的解法
J*a
24 楼
想了一下，还可以优化一点点。
在每次binary之前，用当前最大的面积／当前check的高，来作为high就可以了。
因为high再大的话，即使得出的指小于target，但是面积不会大于当前最大面积。
//area[i][j] is value sum of [0][0]-[i][j];
public int val_cals(a,i,b,j) {
return area[i][j] - area[a][j] - area[i][b] + area[a][j - 1];
}
//This is the calculation of max_area for each right-bottom point (i,j).
for (int a = i - 1; a >= 0; a--) {
if (val_cals(a,i, j-1,j) > target) break;
int low = 0;
int high = j - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (val_cals(a, i, mid, j) > target) low = mid + 1;
else if (val_cals(a, i, mid, j) < target) high = mid - 1;
else {
global_max = Math.max(global_max, (j - mid) * (i - a));
break;
}
}
}
//need to calculate for n*n points to get the global max.
Probably there is some bug.
在每次binary之前，用当前最大的面积／当前check的高，来作为high就可以了。
因为high再大的话，即使得出的指小于target，但是面积不会大于当前最大面积。
//area[i][j] is value sum of [0][0]-[i][j];
public int val_cals(a,i,b,j) {
return area[i][j] - area[a][j] - area[i][b] + area[a][j - 1];
}
//This is the calculation of max_area for each right-bottom point (i,j).
for (int a = i - 1; a >= 0; a--) {
if (val_cals(a,i, j-1,j) > target) break;
int low = 0;
int high = j - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (val_cals(a, i, mid, j) > target) low = mid + 1;
else if (val_cals(a, i, mid, j) < target) high = mid - 1;
else {
global_max = Math.max(global_max, (j - mid) * (i - a));
break;
}
}
}
//need to calculate for n*n points to get the global max.
Probably there is some bug.
f*e
25 楼
楼主， 这题是你自己面的吗？
s*t
26 楼
不是的，看别人面经问的
【在 f**********e 的大作中提到】
: 楼主， 这题是你自己面的吗？
【在 f**********e 的大作中提到】
: 楼主， 这题是你自己面的吗？
s*3
27 楼
rectangle
(b) 这步sub-array with given budget 怎么做到o(n) ? 能说说吗
【在 s*******r 的大作中提到】
: sln 1: brute force
: calculate cost for every possible rectangle and return the maximum rectangle
: within budget.
: complexity: O(n^6)
: O(n^4) rectangles and calc cost for each rectangle is O(n^2)
: sln2: O(n^4)
: 1)fix left and right column of matrix (O(n^2) possibilities)
: 2)for each fixed left and right column
: a)for each row, calc the cost from left to right, as tmp[i] O(n^2)
: b)given 1D array tmp[], find the longest sub-array within budget, can be
h*p
28 楼
http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum
看这个，类似
【在 s****3 的大作中提到】
:
: rectangle
: (b) 这步sub-array with given budget 怎么做到o(n) ? 能说说吗
看这个，类似
【在 s****3 的大作中提到】
:
: rectangle
: (b) 这步sub-array with given budget 怎么做到o(n) ? 能说说吗
s*3
29 楼
我有想到类似的solution 但是不知道怎么把budget 的constraint 用到sub-sum array
中能说说吗?
【在 h**p 的大作中提到】
: http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum
: 看这个，类似
h*p
30 楼
if sum <= budget && sub-matrix的面积 > 所存的最大面积时
then 更新最大面积
array
【在 s****3 的大作中提到】
:
: 我有想到类似的solution 但是不知道怎么把budget 的constraint 用到sub-sum array
: 中能说说吗?
then 更新最大面积
array
【在 s****3 的大作中提到】
:
: 我有想到类似的solution 但是不知道怎么把budget 的constraint 用到sub-sum array
: 中能说说吗?
s*3
31 楼
还是不太懂大牛能够来个代码怎么用DP 和constraint来解吗?
【在 h**p 的大作中提到】
: if sum <= budget && sub-matrix的面积 > 所存的最大面积时
: then 更新最大面积
:
: array
s*3
32 楼
bump 自己顶
r*l
33 楼
这个题是不是最好就是O(n^3)啊？
m*t
34 楼
I can only come up with O(N3) solution
it builds on use O(N) to get the longest continuous sequence for 1D array,
which has total sum less than budget
Then we can get the 1D array for sum of [i:j] rows (so the 1D array is the
same size of number of columns). We can get all combinations in O(N2) time
so total time is O(N3), and space is O(N2)
it builds on use O(N) to get the longest continuous sequence for 1D array,
which has total sum less than budget
Then we can get the 1D array for sum of [i:j] rows (so the 1D array is the
same size of number of columns). We can get all combinations in O(N2) time
so total time is O(N3), and space is O(N2)
r*g
35 楼
我为什么觉得这个题就是N^3的呢？
假设长度为M*N，维护两个竖条AB，表示目前检查的是从A列到B列所有可能的结果，维
护一个长度为M的数组，保存的是当前M行每行的数的和，因为A和B固定，那么只需要M
时间就可以从上扫描一次，基本思路就是，先看第一行是否满足，如果满足，就继续加
第二行，如果超出了，就减去第一行，直到减少到刚刚好，这样看起来时间复杂度是M^
2，但是考虑到可以剪枝，因为是求最大面积，就好像sliding window，最后实际需要
move的次数应该很接近M。假设你的window size增加到K，一旦和超出，你就没有必要
检查window size低于K的了。
然后，从竖条B更新到B+1，只需要M的时间更改每行的和，M的时间扫描。
所以最后结果就是N^2*M。
假设长度为M*N，维护两个竖条AB，表示目前检查的是从A列到B列所有可能的结果，维
护一个长度为M的数组，保存的是当前M行每行的数的和，因为A和B固定，那么只需要M
时间就可以从上扫描一次，基本思路就是，先看第一行是否满足，如果满足，就继续加
第二行，如果超出了，就减去第一行，直到减少到刚刚好，这样看起来时间复杂度是M^
2，但是考虑到可以剪枝，因为是求最大面积，就好像sliding window，最后实际需要
move的次数应该很接近M。假设你的window size增加到K，一旦和超出，你就没有必要
检查window size低于K的了。
然后，从竖条B更新到B+1，只需要M的时间更改每行的和，M的时间扫描。
所以最后结果就是N^2*M。
i*7
36 楼
这个分析的很好啊，如果普通的sliding window高度看作是1的话，这题就是变高度的
sliding window。
M
M^
【在 r*******g 的大作中提到】
: 我为什么觉得这个题就是N^3的呢？
: 假设长度为M*N，维护两个竖条AB，表示目前检查的是从A列到B列所有可能的结果，维
: 护一个长度为M的数组，保存的是当前M行每行的数的和，因为A和B固定，那么只需要M
: 时间就可以从上扫描一次，基本思路就是，先看第一行是否满足，如果满足，就继续加
: 第二行，如果超出了，就减去第一行，直到减少到刚刚好，这样看起来时间复杂度是M^
: 2，但是考虑到可以剪枝，因为是求最大面积，就好像sliding window，最后实际需要
: move的次数应该很接近M。假设你的window size增加到K，一旦和超出，你就没有必要
: 检查window size低于K的了。
: 然后，从竖条B更新到B+1，只需要M的时间更改每行的和，M的时间扫描。
: 所以最后结果就是N^2*M。
sliding window。
M
M^
【在 r*******g 的大作中提到】
: 我为什么觉得这个题就是N^3的呢？
: 假设长度为M*N，维护两个竖条AB，表示目前检查的是从A列到B列所有可能的结果，维
: 护一个长度为M的数组，保存的是当前M行每行的数的和，因为A和B固定，那么只需要M
: 时间就可以从上扫描一次，基本思路就是，先看第一行是否满足，如果满足，就继续加
: 第二行，如果超出了，就减去第一行，直到减少到刚刚好，这样看起来时间复杂度是M^
: 2，但是考虑到可以剪枝，因为是求最大面积，就好像sliding window，最后实际需要
: move的次数应该很接近M。假设你的window size增加到K，一旦和超出，你就没有必要
: 检查window size低于K的了。
: 然后，从竖条B更新到B+1，只需要M的时间更改每行的和，M的时间扫描。
: 所以最后结果就是N^2*M。
相关阅读
请教new construction因为建筑商不能按时close的问题请教关于贷款有人做过air duct balancing吗？南加州适合买房出租吗？有人参加Free House的计划吗？免费住一辈子房子谁买到过这个工具包急求lowes 10% off后院已经没有好草了，怎么除杂草？Home Owner Insurance请教一个跳闸的问题都来吐槽下，前后院有树的房子有哪些活要干？现在房价涨了很多，很少有Deal了请各位大侠帮忙看看这个corner lot的房子新手小白问房贷20包子/5元现金求lowes 10% coupon网星的作者说以后不维护网星了。新手求问agentfurnace下面总有一块水。pingpong, 这个能干啥？Lowe's 10% off Coupon 免费