इस पर कार्य चल रहा
मैं इस समस्या के बारे में सोचा है और मुझे लगता है कि मैं एक हो सकता है O(w*h)
एल्गोरिदम।
विचार इस प्रकार है:
- किसी भी
(i,j)
के लिए स्तंभ j
(i,j)
से शुरू में एक ही मूल्य के साथ कोशिकाओं की सबसे बड़ी संख्या की गणना। इस मान को heights[i][j]
के रूप में स्टोर करें। सभी उप मैट्रिक्स जिसका height > heights[i][j]
जे
- पॉप:
- सभी पंक्ति के लिए उप मैट्रिक्स (एक LIFO)
- के एक खाली वेक्टर बनाएँ: मैं
सभी स्तंभ के लिए
- । क्योंकि ऊंचाई के साथ submatrix>
heights[i][j]
इस सेल पर जारी नहीं रख सकते
- धक्का एक submatrix
(i,j,heights[i][j])
जहां j
है द्वारा परिभाषित farest समन्वय जहां हम ऊंचाई की एक submatrix फिट कर सकते हैं: heights[i][j]
- अद्यतन वर्तमान अधिकतम उप मैट्रिक्स
मुश्किल हिस्सा आंतरिक पाश में है। मैं प्रत्येक सेल के लिए औसत पर O(1)
सुनिश्चित करने के लिए अधिकतम सबविंडो एल्गोरिदम के समान कुछ उपयोग करता हूं।
मैं एक सबूत तैयार करने की कोशिश करूंगा लेकिन इस बीच यहां कोड है।
#include <algorithm>
#include <iterator>
#include <iostream>
#include <ostream>
#include <vector>
typedef std::vector<int> row_t;
typedef std::vector<row_t> matrix_t;
std::size_t height(matrix_t const& M) { return M.size(); }
std::size_t width (matrix_t const& M) { return M.size() ? M[0].size() : 0u; }
std::ostream& operator<<(std::ostream& out, matrix_t const& M) {
for(unsigned i=0; i<height(M); ++i) {
std::copy(begin(M[i]), end(M[i]),
std::ostream_iterator<int>(out, ", "));
out << std::endl;
}
return out;
}
struct sub_matrix_t {
int i, j, h, w;
sub_matrix_t(): i(0),j(0),h(0),w(1) {}
sub_matrix_t(int i_,int j_,int h_,int w_):i(i_),j(j_),h(h_),w(w_) {}
bool operator<(sub_matrix_t const& rhs) const { return (w*h)<(rhs.w*rhs.h); }
};
// Pop all sub_matrix from the vector keeping only those with an height
// inferior to the passed height.
// Compute the max sub matrix while removing sub matrix with height > h
void pop_sub_m(std::vector<sub_matrix_t>& subs,
int i, int j, int h, sub_matrix_t& max_m) {
sub_matrix_t sub_m(i, j, h, 1);
while(subs.size() && subs.back().h >= h) {
sub_m = subs.back();
subs.pop_back();
sub_m.w = j-sub_m.j;
max_m = std::max(max_m, sub_m);
}
// Now sub_m.{i,j} is updated to the farest coordinates where there is a
// submatrix with heights >= h
// If we don't cut the current height (because we changed value) update
// the current max submatrix
if(h > 0) {
sub_m.h = h;
sub_m.w = j-sub_m.j+1;
max_m = std::max(max_m, sub_m);
subs.push_back(sub_m);
}
}
void push_sub_m(std::vector<sub_matrix_t>& subs,
int i, int j, int h, sub_matrix_t& max_m) {
if(subs.empty() || subs.back().h < h)
subs.emplace_back(i, j, h, 1);
}
void solve(matrix_t const& M, sub_matrix_t& max_m) {
// Initialize answer suitable for an empty matrix
max_m = sub_matrix_t();
if(height(M) == 0 || width(M) == 0) return;
// 1) Compute the heights of columns of the same values
matrix_t heights(height(M), row_t(width(M), 1));
for(unsigned i=height(M)-1; i>0; --i)
for(unsigned j=0; j<width(M); ++j)
if(M[i-1][j]==M[i][j])
heights[i-1][j] = heights[i][j]+1;
// 2) Run through all columns heights to compute local sub matrices
std::vector<sub_matrix_t> subs;
for(int i=height(M)-1; i>=0; --i) {
push_sub_m(subs, i, 0, heights[i][0], max_m);
for(unsigned j=1; j<width(M); ++j) {
bool same_val = (M[i][j]==M[i][j-1]);
int pop_height = (same_val) ? heights[i][j] : 0;
int pop_j = (same_val) ? j : j-1;
pop_sub_m (subs, i, pop_j, pop_height, max_m);
push_sub_m(subs, i, j, heights[i][j], max_m);
}
pop_sub_m(subs, i, width(M)-1, 0, max_m);
}
}
matrix_t M1{
{10, 9, 9, 9, 80},
{ 5, 9, 9, 9, 10},
{85, 86, 54, 45, 45},
{15, 21, 5, 1, 0},
{ 5, 6, 88, 11, 10},
};
matrix_t M2{
{10, 19, 9, 29, 80},
{ 5, 9, 9, 9, 10},
{ 9, 9, 54, 45, 45},
{ 9, 9, 5, 1, 0},
{ 5, 6, 88, 11, 10},
};
int main() {
sub_matrix_t answer;
std::cout << M1 << std::endl;
solve(M1, answer);
std::cout << '(' << (answer.w*answer.h)
<< ',' << (answer.j+1) << ',' << (answer.i+1) << ')'
<< std::endl;
answer = sub_matrix_t();
std::cout << M2 << std::endl;
solve(M2, answer);
std::cout << '(' << (answer.w*answer.h)
<< ',' << (answer.j+1) << ',' << (answer.i+1) << ')'
<< std::endl;
}
यदि यह होमवर्क है काम कर हाइलाइटिंग पाने के लिए नहीं कर रहा हूँ, तो कृपया स्पष्ट करें। –
गृहकार्य? आपको समस्या को विस्तार से वर्णन करने की आवश्यकता है उदा। क्या नकारात्मक संख्याएं हैं? मुझे एक गतिशील प्रोग्रामिंग समस्या की तरह लग रहा है। – dirkgently
सबसे बड़ा परिभाषित करें: तत्वों की संख्या? सबसे बड़ी चौड़ाई? सबसे बड़ी ऊंचाई? सबसे बड़ी राशि? – Patrick