Google实习电面

rhett.lhy 发表于 2015-1-19 03:03
恩是的 (n是矩阵的边长)

补充内容 (2015-1-19 03:05):

那得先把histogram编一下，我觉得解释起来挺麻烦的呀，你咋在电话解释清楚的呀？？

applepie11 发表于 2015-1-19 03:06
那得先把histogram编一下，我觉得解释起来挺麻烦的呀，你咋在电话解释清楚的呀？？

啊？这个和histogram不一样的吧……硬要说联系的话，histogram是总体图形是个不规则图形，网格化的话每个格子可以看做是weight为1；这个题是整体矩阵是个规则的正方形/长方形，每个格子里的weight可以是不一样的……

applepie11 发表于 2015-1-19 03:06
那得先把histogram编一下，我觉得解释起来挺麻烦的呀，你咋在电话解释清楚的呀？？

反正我当时直接跟他说这是个经典DP问题，然后就开始编，编完随便解释了两句就过了……

rhett.lhy 发表于 2015-1-19 03:13
反正我当时直接跟他说这是个经典DP问题，然后就开始编，编完随便解释了两句就过了……

我想的是在histogram里找最大矩形，然后套回原题。要是普通dp是n3吧？类似这种http://blog.csdn.net/yusiguyuan/article/details/12877103

你是怎么dp的？

applepie11 发表于 2015-1-19 06:54
我想的是在histogram里找最大矩形，然后套回原题。要是普通dp是n3吧？类似这种http://blog.csdn.net/yusi ...

col[i][j]表示第i竖列index从0到j的和，然后两重循环枚举上下界，循环里面从左往右按照经典的一维问题做，上下界之间每一列的和就是把对应的col[i]减一下就行了

rhett.lhy 发表于 2015-1-19 08:29
col[j]表示第i竖列index从0到j的和，然后两重循环枚举上下界，循环里面从左往右按照经典的一维问题做，上 ...

那就是每一行累加上面所有值吗？枚举上下界目的是什么？能稍微说明一下吗？找矩形吗？
如果是两重循环，每个循环里面不是O(n)吗？难道是O(1) 找最大子段和？