这个题目很俗啦，但确实是不知道题目。这题是从2016ACMer求职群里听到的，不忍放过就贴了过来。如果真的涉及到版权、题目所有权等之类奇怪的东西，请联系我，保证改编到一点都不一样。
描述很简单：一个n*n矩阵，每个元素是一个数，有正有负，求和不超过某个数k的最大子矩阵。
面试官期望能够在20min左右的时间内得到一个O(n^3)时间复杂度的解，GG的面试官。
不贴代码了。说了想法代码本身没啥意义，另外也没有judge的地方。
首先，预处理出每一行的前缀和，O(n^2)枚举左右边界。此时问题变成给n个大小可正可负的数（每个数本身已经是相应行从左边界到右边界的连续子段和），求最大的连续区间使他们的和小于等于某个数。
其次，对于这n个大小可正可负的数，O(n)维护一个（这n个数的）前缀和的单调不减队列，规则如下：
计算前缀和
维护前缀和单调上升队列，一开始放一个0进去
队首出队原则 ： 当新加入队尾的元素A-队首>k时， 队首出队
队尾入队原则 ：保持单调上升队列性质
每次队尾入队的时候， 用队尾-队首更新答案
You actually make it seem really easy together with
your presentation however I in finding this topic to be actually something which I believe I'd never understand.
It kind of feels too complex and very extensive for me.
I'm looking forward in your subsequent post, I will try to get the hang of it!
@Free music Downloads Can the language be an obstacle? And sometimes I wrote too simple..
I do not even understand how I stopped up right here,
but I thought this put up used to be good. I do not understand who you are but certainly you are going to a well-known blogger for those who are not
already. Cheers!
Hi everyone, it's my first visit at this site, and article is
truly fruitful in favor of me, keep up posting these types of
articles.
I am regular reader, how are you everybody? This article posted at this web
page is in fact fastidious.
I'm truly enjoying the design and layout of your site. It's a very easy on the eyes
which makes it much more pleasant for me to come here and
visit more often. Did you hire out a designer to create your theme?
Outstanding work!
It's really a cool and useful piece of info. I'm glad that you shared this useful info with us.
Please stay us informed like this. Thank you for sharing.
Hi, yeah this post is genuinely fastidious and I have learned lot of things from it regarding blogging.
thanks.
I've been browsing online more than three hours these days, yet
I never discovered any interesting article like yours. It's lovely value
sufficient for me. In my opinion, if all web owners and bloggers made good content as you probably did, the net can be a lot more useful than ever before.
Thanks for sharing such a good thought, piece of writing is nice, thats why i have read it fully
I am really thankful to the owner of this website who has shared this fantastic article at at this
place.
I must thank you for the efforts you have put in penning
this blog. I really hope to view the same high-grade content from you in the future as well.
In truth, your creative writing abilities has encouraged me to get my own, personal site now 😉
Greetings I am so glad I found your webpage, I really found you by accident, while
I was looking on Digg for something else,
Regardless I am here now and would just like to say many thanks for a marvelous post
and a all round enjoyable blog (I also love the theme/design), I don’t have
time to look over it all at the minute but I have book-marked it and also added your
RSS feeds, so when I have time I will be back to read
much more, Please do keep up the superb b.
Wonderful blog! I found it while browsing on Yahoo News.
Do you have any suggestions on how to get listed in Yahoo News?
I've been trying for a while but I never seem to get there!
Cheers
I will right away clutch your rss as I can not find your email
subscription hyperlink or newsletter service. Do you have any?
Kindly permit me realize in order that I may just
subscribe. Thanks.
I am sure this paragraph has touched all the internet people, its really really nice article
on building up new blog.
I've been exploring for a little for any high quality articles or blog posts on this kind of
space . Exploring in Yahoo I finally stumbled upon this website.
Reading this info So i am happy to show that I've an incredibly good uncanny feeling I came upon just
what I needed. I such a lot undoubtedly will make sure
to don?t put out of your mind this site and provides it a glance regularly.
It's very simple to find out any topic on web as compared to books, as I found this paragraph at this site.
We absolutely love your blog and find a lot of your post's to be just what I'm
looking for. Do you offer guest writers to write
content for you personally? I wouldn't mind publishing
a post or elaborating on a few of the subjects you write concerning here.
Again, awesome site!
I know this if off topic but I'm looking into starting my
own weblog and was curious what all is needed to get setup?
I'm assuming having a blog like yours would cost a pretty penny?
I'm not very internet smart so I'm not 100% certain. Any recommendations
or advice would be greatly appreciated. Thank you
Excellent beat ! I wish to apprentice whilst you amend your website, how can i subscribe
for a weblog site? The account helped me a acceptable deal.
I have been tiny bit acquainted of this your broadcast provided brilliant transparent concept
I was curious if you ever considered changing the layout of your
site? Its very well written; I love what youve got to say.
But maybe you could a little more in the way of content so people could
connect with it better. Youve got an awful lot of text for
only having one or 2 images. Maybe you could space it out better?