私は次の動的計画法の問題に遭遇しました。
整数のグリッドがあります(負の数を含む)。数値の合計が最大の長方形を見つけます。
マトリックス全体に対してそれを行う方法はありますか?
私はそれを単一の配列について解いたので、最長増加部分列問題が行うことをほぼ追跡しましたが、連続した数についてのみでした。
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タイプのアルゴリズムを検討する必要がありますか?