这个题目很俗啦,但确实是不知道题目。这题是从2016ACMer求职群里听到的,不忍放过就贴了过来。如果真的涉及到版权、题目所有权等之类奇怪的东西,请联系我,保证改编到一点都不一样。

描述很简单:一个n*n矩阵,每个元素是一个数,有正有负,求和不超过某个数k的最大子矩阵。

面试官期望能够在20min左右的时间内得到一个O(n^3)时间复杂度的解,GG的面试官。

不贴代码了。说了想法代码本身没啥意义,另外也没有judge的地方。

首先,预处理出每一行的前缀和,O(n^2)枚举左右边界。此时问题变成给n个大小可正可负的数(每个数本身已经是相应行从左边界到右边界的连续子段和),求最大的连续区间使他们的和小于等于某个数。

其次,对于这n个大小可正可负的数,O(n)维护一个(这n个数的)前缀和的单调不减队列,规则如下:

计算前缀和
维护前缀和单调上升队列,一开始放一个0进去
队首出队原则 : 当新加入队尾的元素A-队首>k时, 队首出队
队尾入队原则 :保持单调上升队列性质
每次队尾入队的时候, 用队尾-队首更新答案