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