自动搬运

查看原文

来自洛谷，原作者为

	ChenHacker 于青春年少，莫虚度时光。

搬运于2025-08-24 21:26:32，当前版本为作者最后更新于2019-08-08 19:25:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这是一名蒟蒻在考场上自己想出来的题解！和下面的大佬的思路都不一样的题解！

我的解法 O(n * n * n * logn),下面那些单调栈是真的牛逼啊。

其实是我把这一题想难了，看下面的O(n * n * n * logn)的解法思路比我简单多了，我这里只是提供一个 与众不同 的解法。

我这个算法是基于暴力优化而来的

首先对于二维的子矩阵问题（比如最大子矩阵），一个常规的思路就是枚举左右区间，然后按照一维的算法来搞

所以我这里只要讲一维的解法就好了（斜眼笑）

谈谈一维的n^2暴力算法

先枚举左端点，然后枚举右端点，然后前缀和O(1)算出sum[l, r]的值如果大于零就跟新ans就好了

然后我这时想到一个馊主意：

对于每一个l，必然有k个r使它可以更新ans，是不是把前缀和sort一下就可以二分了？

然后我很快否定了这个想法，因为就算找到了k个r，我还是得一个一个去更新答案啊。

于是我又想到了前缀最大值，哈哈哈然后这一题就被我A掉了

至于代码，

我有一个码风优美的代码，可惜这里位置太少我贴不下，如果您实在需要，可以email me to 2041026133@qq.com来购买我的代码，目前定价1000000000000000000 rmb, 有需要的快来找我

当然如果你没有那么多钱，您可以先打个暴力拿到60分然后通过代码公开计划在这里查看我的代码

我绝对不会告诉你我的博客上面也有代码的

蒟蒻写题解不易，顺手留赞，感激不尽！