It is the hard level algorithm and I already spent over 60 minutes to think about the algorithm. I like to make it my favorite hard level algorithm. This is Sunday night Feb. 11, 2018 10:32 PM. I wrote down the blog while I mocked interview the peer.
It is hard but I like it
I like to work on the analysis of the algorithm first. I did just download a few algorithm lecture notes and try to identify what is the algorithm. The algorithm is the hard level algorithm on week of code 36. Here is the link.
Feb. 20, 2018
I like to read the solution and then study some of code submission as well. I looked up all submissions scoring 70 and then I found the blog to read.
Here is the blog of the algorithm.
Idea to solve the algorithm
I just copied the idea from the above blog, and then look into some keywords:
- 现在这个最大子段和问题，多出了一次修改，用 dp 记录一下修改有没有用过即可。
- 问题在于要在一列的一个区间中贪心地去掉长度不超过 的子段，使得剩下的和最大（也就是子段和最小）。这个过程在枚举行的下界时用单调队列维护一下，求出最小子段和。