動態規劃：找到具有最大總和的網格中的矩形

你有一個整數網格（所以包括負數）。找出具有最大數字總和的矩形。

任何想法如何爲整個矩陣做？

我解決了它的單個數組，所以我幾乎跟隨了最長的後續子查詢，但僅限於連續的數字。

def array_largest_block(sequence) 
    len = sequence.size 
    parents = [nil]*len 
    my_largest = sequence 
    largest = sequence.max 

    for index in (1...len) 
    if my_largest[index] < my_largest[index] + my_largest[index - 1] 
     my_largest[index] = my_largest[index] + my_largest[index - 1] 
     parents[index] = index - 1 
     largest = [largest, my_largest[index]].max 
    end 
    end 

    end_index_of_largest_block = my_largest.find_index(largest) 
    i = end_index_of_largest_block 
    res = [] 
    res << sequence[i] 
    while !parents[i].nil? 
    i = parents[i] 
    res << sequence[i] 
    end 
    return {l_sum: largest, start: i, end: end_index_of_largest_block} 
end

所以我的想法是，

發現每平方之和的基質（只是1x1的方格）
保存最大的一個可能的答案
運行同樣的事情出發從最小的可能的矩形中計算出所有的直到你找到最大值。 DB是哪一部分。

任何想法？或者如果你們不知道確切的解決方案，我應該看看哪種DP類型的算法？

來源

2012-10-08 Matilda

這可以在O(N^3)中完成，其中N是矩陣的大小。

您基本上選擇矩形的左側和右側列，然後以線性時間掃描行（使用預先計算的總和）。

int totalBestSum = -10000000; 
for (int leftCol = 1; leftCol <= N; leftCol++) 
    for (int rightCol = leftCol; rightCol <= N; rightCol++) 
    { 
     int curSum = 0, curBestSum = -10000000; 
     for (int row = 1; row <= N; row++) { 
     int rowSum = sumBetween(leftCol, rightCol, row); 
     curSum += rowSum; 
     if (curSum > curBestSum) curBestSum = curSum; 
     if (curSum < 0) curSum = 0;     
     } 

     if (curBestSum > totalBestSum) totalBestSum = curBestSum; 
    }

sumBetween是兩列之間的一個特定行返回數字的總和的函數。它可以使用預先計算的總和在不變的時間內實現。

要計算sum陣列：

for (int row = 1; row <= N; row++) 
    for (int col = 1; col <= N; col++) 
     sum[row][col] = sum[row][col - 1] + matrix[row][col];

來源

2012-10-08 17:11:49

謝謝！很乾淨的解決方案 – Matilda

似乎是一個重複的，不過，看這裏：Getting the submatrix with maximum sum?

有可能在O(N^3)做。

爲什麼地球上使用'NP-complete'標籤？：D

來源

2012-10-08 17:11:52 dreamzor

嘿，我覺得DYnamic編程問題是Np完整的，就像knap-sack ... – Matilda

當然這不是真的:) – dreamzor

很好的學習新的東西每天:) – Matilda

動態規劃：找到具有最大總和的網格中的矩形

回答

相關問題