记被自己算法的漏洞坑大的一次
其实并不是很难的一道题，但是思路错了就很容易被某些测试数据整崩，而且还看不到测试数据是什么就更让人崩溃了……
这是我们期中考试的一道题，当时被case28卡住time out了，因为是time out，所以也看不了测试数据。
我最开始的代码是长这个样子的：
其实这个也是前几个case检查出一些错误，改过一两次的结果。
它的大概思路是：每一根柱子都往后找最多能延长几根，但是这样不能找全，因为这根可能在最大矩形的中间位置。其实这个时候很好的一个思路已经呼之欲出了，但我当时没有意识到：最大矩形的高度一定是他所包含的最低柱子的高度，所以对于每根柱子，我们分别向前、向后延长，找到最大面积，最后取最大：这便是最大面积了。
但我当时脑子没有转过来，于是我的思路就是把每根柱子的长度都遍历一遍，每个长度都试一下最多能往右走多少。
这个思路虽然有点蠢，但毕竟可行，于是跑了28个case（第一个case是case 0），可是在case 28，它被卡住，time out了。
我当时只当是他给了一些很大的数，而我的算法有问题比较慢，所以我又转换思路换了种算法写（但其实新算法也不会快）。
新的算法是这样的：
这里的大概想法是这样的：先遍历一遍找到最高柱子，然后从最高高度开始“切”，切出一些矩形，找其中最大的。
不过嘛……这个其实并没有快多少，并且在提交后毫无悬念地停在了case 28:time out.
后来我就没有再管它了。而昨天计概老师开放了“期中考试复盘”的练习，我便又有了看看到底是什么卡住了我的想法。
我想了想，还是用了switch print大法。一个一个答案打表，最后用了200多行switch（只看n和前两个柱子就能区分了，所以是三层switch），整出了一个O(1)的算法（雾
（贴上代码供大家一乐
当我看到case28的内容时，我有点崩溃。
测试数据是这样的：
9
0 0 0 0 0 0 0 0 2147483648
问题得到解决了：不管是哪种算法，都无一例外地会在这里卡死：因为遍历的轮数直接取决于最高柱子的高度。两种算法都会在这里跑2^31次，这谁顶得住啊……
其实我当时考完也有过这种猜测，并且也想到一些解决方法。
其中一个就是：如果他存心为难我，放几个特别高的柱子，那我可以维护一个比较小的数组，里面存放那几个比较高的柱子，先把这几个走一遍，接着再从这里最低的柱子开始往下切。
既然有方法，那我直接用就好了吧。我偷了个懒，觉得可能只有这一个麻烦的东西，于是没有维护数组，而是单挑了一个最大的数出来。当然，其实这应该叫维护了一个2长的数组，因为要从最低的柱子再开始往下切，如果只有一个最大是没有意义的，还应该有第二大，确定开始切的位置。
代码就是这样了：
这个代码非常坚挺，一直活了89个case，但在case 89它倒下了。它也超时了。我估测是这里面不止一个高度离谱的柱子。这没办法了，万一也不止两个呢？还要写几个max呢？
办法自然是有的，比如拷贝一份数组，然后对这个进行局部冒泡排序，找几个比较大的，维护这个数组，然后按着那个方法……
可是有没有一种可能，一开始思路就错了？
我开始反思，而后意识到：确实如此。
对于一根柱子，它不止可以向左，也可以向右，而对每根柱子都如此操作，自然可以获得最大面积。我们甚至也可以给出严谨的证明，用反证法：假如最大面积不是由任何一根柱子向左右延伸而得到，那么我们可以找到这个面积中最矮的柱子，它的高度一定大于矩形高度。将该柱子向左右延伸得到新矩形，两矩形宽度一定相等，而新矩形高于原矩形，则新矩形面积大于原矩形，矛盾。证毕。
（好吧这其实就是一堆废话
于是我们得到了一些很简单的代码：
这个自然还是有一些优化空间的，不过其实没必要再优化了。代码的时间复杂度是，与给出的数据无关了（当然也会有关系，不过不会像前面的代码那样被某些数据卡死了）。
总之就是：王小明，你糊涂啊！！！！！！！
怎么会想到之前那些鬼畜的想法的！！！！！
