Cut a strip - hard level algorithm

Feb. 11, 2018

Introduction

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.

Follow up 

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:

题意

给一个矩阵，可以将其中大小 1 × x (1 ≤ x ≤ k) （纵横均可）变成 0，求操作后最大子矩阵和。

题解

• 如果没有修改，那么就是枚举两行，预处理列的前缀和后就转化为经典的最大子段和了。
• 现在这个最大子段和问题，多出了一次修改，用 dp 记录一下修改有没有用过即可。
• 问题在于要在一列的一个区间中贪心地去掉长度不超过 k 的子段，使得剩下的和最大（也就是子段和最小）。这个过程在枚举行的下界时用单调队列维护一下，求出最小子段和。
• 因为去掉的不一定是列的一部分，还可能是行的一部分，所以要转置后再计算一次。
• 由于操作是必须进行的，矩阵中所有元素都为正数需要特判，强行去掉矩阵中的最小元素。