求最大子矩陣及兩種思路(編輯修改稿)
2024-09-19 06:16 本頁面
【文章內(nèi)容簡介】 m do Begin Sum:=area[x2,y2]area[x11,y2]area[x2,y11]+area[x11,y11]。 If sum0 then updateans(sum)。 End。因此算法的時間復(fù)雜度為O(m2n2)。從上述程序中可以看出，枚舉點的坐標和預(yù)處理的過程有多次重復(fù)操作，也就是說在上述算法的運算中存在著很多冗余運算，如果我們能消除這些冗余運算，將能提高程序效率。下面請看算法二。方法2如何減少冗余呢？我們不妨這樣的思考，上面的枚舉實際將所有的矩形，不管有用無用全部枚舉了出來。其實，對于大部分無用的矩形是可以不需要枚舉就可以排除在最優(yōu)解之外的，而有用的矩形指的是那些極大化矩形。所謂極大化的矩形就是指那些不能再通過擴展邊來再次增大面積的矩形。這樣的矩形之所以無法再擴展是因為它們的四條邊要么靠障礙物，要么靠著邊界。例如下圖中A的黃色部分就是一個極大化矩形，而B不是（它的右邊界還可以向右延伸到邊界），因此我們可以根據(jù)這一特點來找到所有的極大化矩形。圖2 極大化矩形為了完成尋找極大化矩形的工作，我們先來看一個這樣的子問題：問題描述：給出若干個連在一起的高塔，已知每個塔
畢業(yè)設(shè)計相關(guān)推薦
鄂ICP備17016276號-1