homework-02

      上一次解决了一维下的最大子序列和的问题,紧接着老师提到了下面的迫使无数同学退课的难题——二维下,甚至于伪三维情况下最大子序列的和,运行参数[h][v][a],其中h选项代表给定的二维表是水平循环的,v代表给定的二维表是垂直循环的,a表示结果可以突破矩形的限制,寻找一个最大的连通块,而非矩形。。尽管传说中的暴力搜索可以通过浪费时间来完成这些,但是还是思索一种合适的算法,至少将复杂的从O(n^3)降下来,所以就在想能不能类比一维时的处理方法,

1,

      然后发现实际上第二个问号中子序列全部以矩阵的形式存在。二维的情况就是讲二维转换为一维。即将n行m列的二维数组转换为n^2个长度为m的一维数组。时间复杂度为O(m*n^2)。

2

       有了上面的基础我们再考虑/v和/h的情况,这两种情况实际上是等价的,因此我们仅考虑/h的情况,/h选项表示二维表在水平方向上时循环连通的,我采用了在水平方向上扩展一次二维表的方法,扩展如图

-----------》

3

     实际上可以发现,包括甜甜圈在内都可以转化为二维,更进一步就是一维进行处理

4,

      至于连通图。。。实在是不知道怎么去啃那个硬茬,暴力搜索估计都不可能,容十一思索思索,彻底搞清这个问题

原文地址:https://www.cnblogs.com/fireyjy/p/3348228.html